UVA 10129 Play On Words 一道题同时学会欧拉回路和并查集
这道题是一道学习并查集和欧拉回路的好题。
也可以用另外的dfs+建图的方式，不过不如并查集好用，强烈推荐学习一下并查集，很优美的一个数据结构，后面有时间可能也会写一写这种算法笔记，先引用一下别人的文章
可以先借助这篇文章了解一下欧拉回路
欧拉回路
然后并查集的知识可以借助这一篇
并查集
然后这道题可以把每一个单词看成一条有向边，然后统计出度入度，统计连通集内点的个数，然后判断入度出度是否符合，然后判断是否所有点在同一连通集内部，得出答案即可。
最后说一下我踩得坑，又把=写成了==,debug了得20分钟，急死了也找不出来，以后debug的时候一定要先全文通读一遍了，看看有没有这种错误。
# include# include# include# includeusing namespace std;const int N=30;int n,T;bool st[N];int din[N],dout[N];int p[N];char str[10010];int find(int x){ if(x!=p[x]) { p[x]=find(p[x]); } return p[x];}int main(){ cin>>T; while(T--) { cin>>n; for(int i=0;i<26;i++) { p[i]=i; } memset(din,0,sizeof din);memset(dout,0,sizeof dout);memset(st,0,sizeof st); for(int i=0;i<n;i++) { scanf("%s",str); int len=strlen(str); int x1=str[0]-'a';int x2=str[len-1]-'a'; din[x1]++,dout[x2]++; p[find(x1)]=find(x2); st[x1]=true;st[x2]=true; } bool success=true; int in=0,out=0; for(int i=0;i<26;i++) { if(din[i]==dout[i]+1) { in++; } else if(din[i]+1==dout[i]) { out++; } else if(din[i]!=dout[i]) { success=false; break; } } if (success && !(!in && !out || in == 1 && out == 1)) success = false; int rep=-1; for(int i=0;i<26;i++) { if(st[i]) { if(rep==-1) { rep=find(i); } else if(rep!=find(i)) { success=false; break; } } } if(!success) puts("The door cannot be opened."); else puts("Ordering is possible."); }}
