Play on Words
题意：n个单词，问能否收尾相连形成一条链。
把单词首尾字母看做点，单词内部连一条边，问是否存在欧拉路径。
用并查集，当且仅当只有一个点的出度比入度大1一个点的入度比出度大1其它点出度和入度相等时存在欧拉路径。
1 #include<cstdio> 2 #include<cstring> 3 #include<set> 4 #include<iostream> 5 #include<cctype> 6 #include<string> 7 #include<sstream> 8 #include<algorithm> 9 #include<map> 10 #define LL long long 11 using namespace std; 12 const int maxn=100010; 13 int in[30],out[30]; 14 int f[30]; 15 set<int> si; 16 void init() 17 { 18 for(int i=0;i<30;i++) 19 { 20 in[i]=0; 21 out[i]=0; 22 f[i]=i; 23 } 24 } 25 26 int gf(int x) 27 { 28 return x==f[x]?x:f[x]=gf(f[x]); 29 } 30 31 void uni(int a,int b) 32 { 33 int pa=gf(a); 34 int pb=gf(b); 35 f[pa]=pb; 36 } 37 string s; 38 int main() 39 { 40 int t; 41 scanf("%d",&t); 42 while(t--) 43 { 44 int ok=1; 45 si.clear(); 46 init(); 47 int n; 48 int a,b; 49 int ctin=0,ctout=0,ct=0; 50 scanf("%d",&n); 51 for(int i=0;i<n;i++) 52 { 53 cin>>s; 54 a=s[0]-'a'; 55 b=s[s.length()-1]-'a'; 56 si.insert(a); 57 si.insert(b); 58 in[a]++; 59 out[b]++; 60 if(gf(a)!=gf(b)) uni(a,b); 61 } 62 int u=gf(a); 63 for(set<int> ::iterator it=si.begin();it!=si.end();it++) 64 { 65 if(gf(*it)!=u) ct++; 66 if(ct>0) {ok=0;break;} 67 if(in[*it]-out[*it]==1) ctin++; 68 else if(in[*it]-out[*it]==-1) ctout++; 69 else if(in[*it]-out[*it]>1||in[*it]-out[*it]<-1) {ok=0;break;} 70 if(ctin>1||ctout>1) {ok=0;break;} 71 } 72 73 if(ok) puts("Ordering is possible."); 74 else puts("The door cannot be opened."); 75 } 76 }