杭电ACM1116――Play on Words~~欧拉路径与欧拉回路

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int par[30], indegree[30], outdegree[30]; //par为并查集，indegree为入度，outdegree为出度 bool vis[30]; //vis为该顶点出现过的标记 int finds(int x) //并查集的查找函数 { int r = x; while(r != par[r]) r = par[r]; int i = x, j; while(i != r) //路径紧缩 { j = par[i]; par[i] = r; i = j; } return r; } void join(int x, int y) //并查集的合并函数 { int fx = finds(x); int fy = finds(y); if(fx != fy) par[fy] = fx; } int main() { int t, n, i; char str[1005]; scanf("%d", &t); while(t--) { memset(indegree, 0, sizeof(indegree)); //初始化各个数组 memset(outdegree, 0, sizeof(outdegree)); memset(vis, false, sizeof(vis)); for(i = 0; i < 30; i++) //初始化并查集 par[i] = i; scanf("%d", &n); while(n--) { scanf("%s", str); int len = strlen(str); join(str[0] - 'a', str[len - 1] - 'a'); //合并出现的顶点 indegree[str[len - 1] - 'a']++; //相应的入度+1 outdegree[str[0] - 'a']++; //相应的出度+1 vis[str[0] - 'a'] = true; //标记该顶点出现过 vis[str[len - 1] - 'a'] = true; } int flag = 0, tag = 0, a = 0, b = 0; //flag来判图是不是连通，tag为图中顶点入度不等于出度的个数 <span style="white-space:pre"> </span>//a为入度大出度1的点的个数，b为出度大入度1的点的个数 for(i = 0; i < 30; i++) //判连通 { if(vis[i] && par[i] == i) flag++; } if(flag > 1) //不连通，直接输出 { printf("The door cannot be opened. "); } else { for(i = 0; i < 30; i++) //查找tag，a， b 的个数 { if(vis[i] && indegree[i] != outdegree[i]) { tag++; } if(vis[i] && indegree[i] - outdegree[i] == 1) a++; if(vis[i] && outdegree[i] - indegree[i] == 1) b++; } if(tag == 0) //tag = 0，存在欧拉回路 printf("Ordering is possible. "); else if(a == b && a == 1 && tag == 2) //a = 1 && b = 1 && tag = 2.存在欧拉路径 printf("Ordering is possible. "); else printf("The door cannot be opened. "); } } return 0; }