输入n(n<=10000）个单词，是否可以把这些单词排成一个序列，使得每个单词的第一个字母和上一个单词的最后一个字母相同（例如：acm\malform\mouse）。每个单词最多包含1000个小写字母。输入中可以用重复单词
【分析】
思路：欧拉道路的应用。欧拉道路，即“一笔画”，从图中一结点出发走一条道路，每条边恰好经过一次。
首先要判断图是连通的。
对于无向图，最多只有两个奇点（度数为奇数）。且从一奇点出发，到另一奇点终止；若无奇点，则可从任意点出发，最终定会回到该点（欧拉回路）。
对于有向图，最多只能有两个点的入度不等于出度，且必须其中一点的出度恰好比入度大1（作为起点），另一点的入度比出度大1（作为终点）。对于有向图的连通性判断，白书上和网上题解都是说用基图（无向图）来判断连通性。自己想了下，用有向图来判断连通性肯定也是可以的，因为有向图如果不连通肯定也是不能形成欧拉道路的；但是有向图的连通性不好判断，比如一个链式的有向图，你比如从第一个起点去搜，才能知道它是连通的，你从其他点出发就不能得到连通的结论。
对于该题，可以把单词的首字母和尾字母看成顶点，一个单词，它的首尾字母存在一条有向边。这样，问题即为，每条边恰好经过一次。
因为字母作为顶点，题目里给的最多26个。 连通性的判断可以用bfs或dfs遍历即可，可以从某个入度或出度不为0（即26个字母中在该示例中出现了的字母）的顶点出发进行一次遍历，遍历结束后如果还有“出现了的字母”没被访问到，则说明不连通；或者也可以用dfs进行遍历所有的出现了的字母，然后计数，（相当于之前uva 572 求八连通块的个数）个数大于1则说明不连通。 需要注意，在一些地方，要判断26个字母每个字母是否出现。 在判断入度比出度大1、出度比入度大1后，不要忘了所有的点入度都等于出度也是可以的~
【代码】参考http://blog.csdn.net/primoblog/article/details/8471199
#include<stdio.h> #include<string.h> int str[27][27], visit[27], du[27][2];//str为邻接矩阵，记录两个节点是否连通，数组du用于记录字母的出度与入度 void read() { //读取字符串，记录开头与结尾的字母 int n; char por, tear, temp; scanf("%d", &n); getchar(); while (n--) { scanf("%c", &por); du[por - 'a'][1]++; while ((temp = getchar()) != '\n') tear = temp; du[tear - 'a'][0]++; str[por - 'a'][tear - 'a'] = 1; } } void dfs(int s) { //深搜，找是否有通路 visit[s] = 1; for (int i = 0; i < 26; i++) { if (str[s][i] && !visit[i]) dfs(i); } } int solve() { int head = -1, tear = -1; for (int i = 0, count = 0; i < 26; i++) {//检查出度与入度，是否满足出度与入度相等，否则最多相差1 if (du[i][0] != du[i][1]) { if (du[i][0] - du[i][1] >= 2 && du[i][0] - du[i][1] <= -2) return 0; else { count++; if (du[i][1] - du[i][0] == 1) head = i; else tear = i; } } if (count > 2)return 0;//如果出现多个出度与入度相差1的节点，则肯定不能有且只有一条通路 } if (head == -1 && tear == -1)//如果是欧拉回路的话 { for (int i = 0; i < 26;i++) if (du[i][0]){ dfs(i); break; } } else if (head == -1 || tear == -1)return 0; else dfs(head);//否则从头开始搜索 for (int i = 0; i < 26;i++) if (((du[i][0] + du[i][1]) && visit[i]) || (!(du[i][0] + du[i][1]) && !visit[i]));//看其是否为通路（即有度的节点必须被访问到） else return 0; return 1; } int main() { int t; scanf("%d", &t); while (t--) { memset(str, 0, sizeof(str)); memset(visit, 0, sizeof(visit)); memset(du, 0, sizeof(du)); read(); if (solve()) puts("Ordering is possible"); else puts("The door cannot be opened."); } return 0; }