主要是歐拉回路的基礎知識，用并查集加工處理

注意歐拉回路和并查集的細節判斷

不能粘貼復制，一定要理解之后再敲一遍代碼，否則浪費更多的時間

#include <stdio.h> #include <string.h>int vis[30],in[30],out[30],father[30];int findx(int t) {if(father[t]!=t)father[t]=findx(father[t]);return father[t]; }void merge(int v,int g) {int x,y;x=findx(v);y=findx(g);if(x!=y)father[x]=y; }int main() {int n,m,s,e,bcn,i,j;int p[30];scanf("%d",&n);while(n--){char a[1001];scanf("%d",&m);memset(out,0,sizeof(out));memset(in,0,sizeof(in));memset(vis,0,sizeof(vis));for(i=0;i<26;i++)father[i]=i;while(m--){scanf("%s",a);s=a[0]-'a';e=a[strlen(a)-1]-'a';merge(s,e);out[s]++;in[e]++;vis[s]=1;vis[e]=1;}for(i=0;i<26;i++)father[i]=findx(i);for(bcn=0,i=0;i<26;i++){if(father[i]==i&&vis[i])bcn++;}//printf("%d\n",bcn);if(bcn>1){printf("The door cannot be opened.\n"); continue;}for(j=0,i=0;i<26;i++){if(vis[i]&&out[i]!=in[i])p[j++]=i;}if(j==0){printf("Ordering is possible.\n"); continue;}if(j==2 && ( (out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1 )|| (out[p[1]]-in[p[1]]==1 && in[p[0]]-out[p[0]]==1 )) ) { printf("Ordering is possible.\n"); continue; } printf("The door cannot be opened.\n"); }return 0; }

　　

轉載于:https://www.cnblogs.com/jackes/archive/2012/03/29/2423825.html

總結

以上是生活随笔為你收集整理的hdu 1116 欧拉回路 并查集 一组字符串能否首尾相连成一个字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。