本文链接:http://www.cnblogs.com/Ash-ly/p/5398627.html
题意：
输入N(N <= 100000)个单词，是否可以把所有这些单词排成一个序列，使得每个单词的第一个字母和上一个单词的最后一个字母相同(例如:acm,malform,mouse)。每个单词最多包含 1000 个小写字母。输入中可以有重复的单词。
思路：
把一个字母的两端开成节点，单词看成有向边，若问题有借，当且仅当图中存在欧拉通路。所有只需要判断由单词而构建的图是否存在欧拉通路，由于是有向边，所以利用有向图欧拉通路的判定就可以了。
判定条件
(1):底图是连通图
(2):可以有两个奇点，其中一个出度比入度大 1，另外一个入度比出度大1.
对于条件1,在这里用并查集判断了,条件2统计每个点的出度，入度，加以判断就行了.
代码：
#include#include #include #include #include #include #include using namespace std; const int maxV = 29;int m;int pre[maxV + 7];int outdegree[maxV + 7];int indegree[maxV + 7];int Find(int x){ return x == pre[x] ? x : pre[x] = Find(pre[x]); }//并查集的查找void initPre(){ for(int i = 0; i <= maxV; i++) pre[i] = i; }//初始化并查集的数组int mix(int x, int y)//并查集的合并{ int fx = Find(x), fy = Find(y); if(fx != fy) pre[fx] = fy; }bool isConnct()//判断图是否连通，即所有的点都在一个集合里面{ int cnt = 0; for(int i = 1; i <= maxV; i++)if( (outdegree[i] != 0 || indegree[i] != 0) && pre[i] == i) cnt++; if(cnt == 1)return true; return false;}bool isEulur()//是否存在欧拉通路{ int cnt = 0; int flag = 0; for(int i = 1; i <= 26; i++) if((outdegree[i] != 0 || indegree[i] != 0) && (indegree[i] != outdegree[i]))//判断奇点，方法不唯一。 { cnt++; flag += (indegree[i] - outdegree[i]); if(flag > 1 || flag < -1) return false; } if(cnt == 0 || cnt == 2 && flag == 0) return true; return false;}int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d", &m); initPre(); memset(indegree, 0, sizeof(indegree)); memset(outdegree, 0, sizeof(outdegree)); for(int i = 1; i <= m; i++) { char word[1000 + 7]; scanf("%s", word); int u = word[0] - 'a' + 1; int len = strlen(word); int v = word[len - 1] - 'a' + 1; mix(u, v); ++outdegree[u]; ++indegree[v]; } if(isEulur() && isConnct()) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0;}