http://acm.hdu.edu.cn/showproblem.php?pid=1116
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int N=30; 8 int father[N],vis[N]; 9 int find(int x)//查找根10 {11 if(father[x]!=x)12 father[x]=find(father[x]);13 return father[x];14 }15 void make(int a,int b)//合并操作16 {17 int f1=find(a);18 int f2=find(b);19 if(f1!=f2)20 father[f1]=f2;21 }22 23 int main()24 {25 //freopen("in.txt","r",stdin);26 int t;27 cin>>t;28 while(t--)29 {30 int out[N],in[N],p[N];31 memset(in,0,sizeof(in));32 memset(out,0,sizeof(out));33 memset(vis,0,sizeof(vis));34 int n;35 for(int i=0;i<26;i++)36 father[i]=i;//数组赋初值37 cin >> n;38 while(n--)39 {40 char str[1005];41 cin>>str;42 int a=str[0]-'a';43 int b=str[strlen(str)-1]-'a';44 out[a]++;45 in[b]++;46 make(a,b);//合并操作47 vis[a]=vis[b]=1;48 }49 for(int i=0;i<26;i++)50 father[i]=find(i);//寻找每个点的根节点51 int cnt=0;52 for(int i=0;i<26;i++)53 {54 if(vis[i] && father[i]==i)//确定有几颗树55 cnt++;56 }57 if(cnt>1)58 {59 printf("The door cannot be opened.\n");60 continue;61 }62 int j=0;63 for(int i=0;i<26;i++)64 {65 if(vis[i] && out[i]!=in[i])//找起点和终点66 p[j++]=i;67 }68 if(j==0)//环69 {70 printf("Ordering is possible.\n");71 continue;72 }73 if(j==2 && ((out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1 ) ||74 (in[p[0]]-out[p[0]]==1 && out[p[1]]-in[p[1]]==1 ) ) )75 { //起点和终点的判断76 printf("Ordering is possible.\n");77 continue;78 }79 printf("The door cannot be opened.\n");80 }81 return 0;82 }