hdu1116

http://acm.hdu.edu.cn/showproblem.php?pid=1116

 #include<stdio.h>

 #include<math.h>

 #include<string.h>

 #include<stdlib.h>

 #include<iostream>

 using namespace std;

 const int N=;

 int father[N],vis[N];

 int find(int x)//查找根

 {

     if(father[x]!=x)

     father[x]=find(father[x]);

     return father[x];

 }

 void make(int a,int b)//合并操作

 {

     int f1=find(a);

     int f2=find(b);

     if(f1!=f2)

     father[f1]=f2;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int t;

     cin>>t;

     while(t--)

     {

         int out[N],in[N],p[N];

         memset(in,,sizeof(in));

         memset(out,,sizeof(out));

         memset(vis,,sizeof(vis));

         int n;

         for(int i=;i<;i++)

         father[i]=i;//数组赋初值

         cin >> n;

         while(n--)

         {

             char str[];

             cin>>str;

             int a=str[]-'a';

             int b=str[strlen(str)-]-'a';

             out[a]++;

             in[b]++;

             make(a,b);//合并操作

             vis[a]=vis[b]=;

         }

         for(int i=;i<;i++)

         father[i]=find(i);//寻找每个点的根节点

         int cnt=;

         for(int i=;i<;i++)

         {

             if(vis[i] && father[i]==i)//确定有几颗树

             cnt++;

         }

         if(cnt>)

         {

             printf("The door cannot be opened.\n");

             continue;

         }

         int j=;

         for(int i=;i<;i++)

         {

             if(vis[i] && out[i]!=in[i])//找起点和终点

             p[j++]=i;

         }

         if(j==)//环

         {

             printf("Ordering is possible.\n");

             continue;

         }

         if(j== && ((out[p[]]-in[p[]]== && in[p[]]-out[p[]]== ) ||

                     (in[p[]]-out[p[]]== && out[p[]]-in[p[]]== ) ) )

         {//起点和终点的判断

             printf("Ordering is possible.\n");

             continue;

         }

         printf("The door cannot be opened.\n");

     }

     return ;

 }