图|[编程题]单词接龙欧拉路径一笔画问题图|nowcoder

问题描述牛客网：
http://www.nowcoder.com/questionTerminal/417f534ca33f4bc7ba8ef716c980f839
拉姆刚开始学习英文单词，对单词排序很感兴趣。
如果给拉姆一组单词，他能够迅速确定是否可以将这些单词排列在一个列表中，使得该列表中任何单词的首字母与前一单词的为字母相同。
你能编写一个程序来帮助拉姆进行判断吗？
输入描述:
输入包含多组测试数据。
对于每组测试数据，第一行为一个正整数n，代表有n个单词。
然后有n个字符串，代表n个单词。
保证：
2<=n<=200,每个单词长度大于1且小于等于10,且所有单词都是由小写字母组成。
输出描述:
对于每组数据，输出”Yes”或”No”
输入例子:
3
abc
cdefg
ghijkl
4
abc
cdef
fghijk
xyz
输出例子:
Yes
No
问题分析如果是必须按顺序判断，则比较简单，直接判断后一个单词的开头是否能接上上一个单词的结尾即可，如代码1。
如果不按顺序，则是一个“一笔画”问题（欧拉回路），需要建立图的模型求解，如可以查看牛客网的“西电学生”的java代码，贴在了代码2中。
或者参考”Robot_luo”的cpp代码（代码3）。
参考
一笔画问题
有向图的连通性及其分类
算法专题：欧拉回路

连通的无向图 G 有欧拉路径的充要条件是： G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。
连通的无向图 G 是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数。[2]。
一个连通的有向图可以表示为一条从顶点 u到 v的（不闭合的）欧拉路径的充要条件是： u的出度（从这个顶点发出的有向边的数量）比入度（指向这个顶点的有向边的数量）多1，v的出度比入度少1，而其它顶点的出度和入度都相等。
设D=(V,E)为一个有向图。若D的基图是连通图，则称D是弱连通图，简称为连通图。若vi,vj∈V ，vi→vj与vj→vi至少成立其一，则称D是单向连通图。若均有vi<->vj，则称D是强连通图。

代码1

#include #include #include using namespace std; int main() { int num; while (cin >> num) { vector v; for (int i = 0; i < num; i++) { string s; cin >> s; v.push_back(s); } string nowstr = v[0]; char nowend = nowstr[nowstr.size()-1]; int i; for (i = 1; i < num; i++) { nowstr = v[i]; //cout << nowstr[0] << " " << nowend << endl; if (nowstr[0] != nowend) { cout << "No" << endl; break; } nowend = nowstr[nowstr.size()-1]; } if (i == num) cout << "Yes" << endl; } return 0; }

代码2

import java.util.*; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); while (scan.hasNext()) { int n = scan.nextInt(); String[] arr = new String[n]; for (int i = 0; i < n; i++) arr[i] = scan.next(); System.out.println(canArrangeWords(n, arr)); } scan.close(); }public static String canArrangeWords(int n, String[] arr) { // 26个英文字母看作26个点,用整数0-25来表示 int[][] directedGraph = new int[26][26]; // 邻接矩阵表示有向图 int[] inDegree = new int[26]; // 顶点入度 int[] outDegree = new int[26]; // 顶点出度 boolean[] hasLetter = new boolean[26]; // 标记字母是否出现过 boolean hasEuler = true; // 有狭义欧拉路径或欧拉回路标志 for (int i = 0; i < n; i++) { String word = arr[i]; char firstLetter = word.charAt(0); char lastLetter = word.charAt(word.length() - 1); outDegree[firstLetter - 'a']++; inDegree[lastLetter - 'a']++; directedGraph[firstLetter - 'a'][lastLetter - 'a'] = 1; // 有向图 hasLetter[firstLetter - 'a'] = true; hasLetter[lastLetter - 'a'] = true; } int startNum = 0; int endNum = 0; for (int vertex = 0; vertex < 26; vertex++) { if (outDegree[vertex] - inDegree[vertex] == 1) // 起点 startNum++; if (inDegree[vertex] - outDegree[vertex] == 1) // 终点 endNum++; if (Math.abs(inDegree[vertex] - outDegree[vertex]) > 1) { hasEuler = false; break; } } boolean isEulerPath = (startNum == 1 && endNum == 1); // 这里指狭义上的欧拉路径，不包括欧拉回路 boolean isEulerCircuit = (startNum == 0 && endNum == 0); // 欧拉回路 if ((!isEulerPath) && (!isEulerCircuit)) { // 既不是欧拉路径也不是欧拉回路 hasEuler = false; } // 判断是否弱连通 int vertexNum = 0; // 点的数量 for (int letter = 0; letter < 26; letter++) { if (hasLetter[letter]) { vertexNum++; } } int firstWordFirstLetter = arr[0].charAt(0) - 'a'; // 以第一个单词的首字母作为起点 hasEuler = hasEuler && isConnected(firstWordFirstLetter, vertexNum, directedGraph); if (hasEuler) { return "Yes"; } else { return "No"; } }// 判断有向图是否弱连通 public static boolean isConnected(int start, int vertexNum, int[][] directedGraph) { int[][] undirectedGraph = new int[26][26]; // 把有向图转换成无向图 for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) { if (directedGraph[i][j] == 1) { undirectedGraph[i][j] = 1; undirectedGraph[j][i] = 1; } } } Queue queue = new LinkedList(); boolean[] passedVertex = new boolean[26]; queue.offer(start); // 从起点开始进行广度优先搜索，把路过的边都拆掉 while (!queue.isEmpty()) { int currentVertex = queue.peek(); passedVertex[currentVertex] = true; queue.poll(); for (int vertex = 0; vertex < 26; vertex++) { if (undirectedGraph[currentVertex][vertex] == 1 && passedVertex[vertex] == false) { undirectedGraph[currentVertex][vertex] = 0; undirectedGraph[vertex][currentVertex] = 0; queue.offer(vertex); } } } int passedVertexNum = 0; for (int vertex = 0; vertex < 26; vertex++) { if (passedVertex[vertex]) { passedVertexNum++; } } // 遍历到所有的点，证明无向图是连通的 if (passedVertexNum == vertexNum) { return true; } else { return false; } } }

代码3 这题如果是直接按顺序就很简单，判断下当前单词开头是不是等于前一个单词结尾就行了。
但是如果是可以调换顺序，就变成了一个一笔画的问题，判断是否存在欧拉通路
将单词建成一副图，取出每个单词的第一个字母和最后一个字母，连一条有向边。
然后根据欧拉通路的性质，判断下每个点的入度出度（奇数度的点不能大于2）
最后bfs判断图是否是连通图

#include #include #include #include #include using namespace std; char str[300]; int g[30][30]; int In[30]; int Out[30]; int num[30]; void init() { memset(g, 0, sizeof(g)); memset(In, 0, sizeof(In)); memset(Out, 0, sizeof(Out)); memset(num, 0, sizeof(num)); }bool bfs(int s,int n) { queue q; q.push(s); int mark[30]; memset(mark, 0, sizeof(mark)); while (!q.empty()) { int front = q.front(); mark[front] = 1; q.pop(); for (int i = 0; i < 30; i++) { if (g[front][i] && mark[i] == 0) { g[front][i] = 0; q.push(i); } } } int ha = 0; for (int i = 0; i < 30 ; i++) if (mark[i]) ha++; if (ha==n) return true; return false; }int main() { int n,s; while (cin >> n) { init(); bool temp = true; for (int i = 0; i> str; int len = strlen(str); Out[str[0] - 'a']++; In[str[len - 1] - 'a']++; g[str[0] - 'a'][str[len - 1] - 'a'] = 1; g[str[len - 1] - 'a'][str[0] - 'a'] = 1; if (num[str[0] - 'a'] == 0) num[str[0] - 'a'] = 1; if (num[str[len - 1] - 'a'] == 0) num[str[len - 1] - 'a'] = 1; s = str[0] - 'a'; }int sum1 = 0; int sum2 = 0; for (int i = 0; i < 30; i++) { if ((In[i] - Out[i]) >=1) sum1++; if ((In[i] - Out[i]) <= -1) sum2++; if (abs(In[i] - Out[i])>1) temp = false; } if (sum1 >= 2 || sum2 >= 2) temp = false; int ha = 0; for (int i = 0; i < 30; i++) { if (num[i] == 1) ha++; } temp = temp & bfs(s,ha); if (temp) cout << "Yes" << endl; else cout << "No" << endl; } }

小结 【图|[编程题]单词接龙欧拉路径一笔画问题】总的来说，如果要求有向图存在欧拉路径，首先要是弱连通图。然后，除了起点和终点以外，其他点的入度和出度相等。而且起点的出度比入度大1，终点的入度比出度大1。