题目链接：http://poj.org/problem?id=1386 题意：给你n个字符串，问你他们是否能首尾拼接起来，其实也就是问你，只看开头后结尾的字母所构成的图是否有欧拉路或者欧拉回路 解析：对于有向图来说，欧拉回路的存在条件是图联通，且每一点的出度等于入度，欧拉路的条件是，图联通，起点的出度大于入度，终点的入度大于出度，其余点出度和入度相等。所以用并查集判断图联通，度用数组记录下就好
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <vector> using namespace std; const int maxn = 1e5+100; int vis[100],fa[100]; int du[100]; void init() { memset(vis,0,sizeof(vis)); memset(du,0,sizeof(du)); for(int i=0;i<100;i++) fa[i] = i; } int findFa(int x) { if(x==fa[x]) return x; return fa[x] = findFa(fa[x]); } void merge(int u,int v) { int t1 = findFa(u); int t2 = findFa(v); if(t1!=t2) fa[t1] = t2; } int main(void) { int t; scanf("%d",&t); while(t--) { int n; init(); scanf("%d",&n); for(int i=0;i<n;i++) { char tmp[1005]; scanf("%s",tmp); int len = strlen(tmp); int s = tmp[0]-'a'+1; int t = tmp[len-1]-'a'+1; vis[s] = 1;vis[t] = 1; merge(s,t); du[s]++;du[t]--; } int root = 0; vector<int>d; for(int i=0;i<100;i++) { if(vis[i]) { if(fa[i]==i) root++; if(du[i]!=0) d.push_back(du[i]); } } if(root==1 && (d.size()==0 || (d.size()==2 && (d[0]==1 || d[0]==-1)))) puts("Ordering is possible."); else puts("The door cannot be opened."); } return 0; }