POJ 1386 欧拉路的判定

题意：

      给你n个单词，问你有没有一种排列方式可以所有单词的首部是相邻单词的尾部。

思路：

      这个题目还挺基础的，就是个欧拉的判定，首先对于每一个单词，我们把他抽象成边，每个单词两端的字母抽象成边的两个点，这样就是判断有向图是否可以组成欧拉回路或者欧拉路径了，如果能那么就能达到题目要求，如果不能就不行，还有一点就是在判定欧拉的时候记得先并查集一遍，防止图不连通。

提示下：在连通图下，有向图欧拉回路的判定是所有点的入度等于出度。

              在连通图下，有向图欧拉路径的判定是有一个点的入度比出度大一，有一个点的出度比入度大一，其余的入度等于出度。

               在连通图下，无向图的欧拉回路判定是所有点的度数为偶数。

               在连通图下，无向图的欧拉路径判定是有两个点的度数是奇数，其余的全是偶数。

              

#include<stdio.h> #include<string.h>#define N 50int mer[N] ,mark[N]; int in[N] ,out[N]; char str[1100];int finds(int x) {return x == mer[x] ? x : mer[x] = finds(mer[x]); }int main () {int t ,n ,i;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= 26 ;i ++)mer[i] = i,in[i] = out[i] = mark[i] = 0;while(n--){scanf("%s" ,str);int a = str[0] - 'a' + 1;int b = str[strlen(str) - 1] - 'a' + 1;out[a] ++ ,in[b] ++;mer[finds(a)] = finds(b);mark[a] = mark[b] = 1;}int s = 0;for(i = 1 ;i <= 26 ;i ++){if(!mark[i]) continue;if(mer[i] == i) s ++;}if(s != 1){puts("The door cannot be opened.");continue;}int s1 = 0,s2 = 0 ,s3 = 0 ,ss = 0;for(i = 1 ;i <= 26 ;i ++){if(!mark[i])continue;if(in[i] - out[i] == 1) s1 ++;if(in[i] - out[i] == -1) s2 ++;if(in[i] == out[i]) s3 ++;ss ++;}if(s1 + s2 + s3 == ss){if(!s1 && !s2 || s1 == 1 && s2 == 1)puts("Ordering is possible.");}else puts("The door cannot be opened.");}return 0; }

 

总结

以上是生活随笔为你收集整理的POJ 1386 欧拉路的判定的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。