HDU1116图论

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

 #include<stdio.h>

 #include<algorithm>

 #include<iostream>

 #include<string.h>

 using namespace std;

 const int M=;

 int fa[M],vis[M],in[M],out[M],ans[M];

 char ch[];

 int fin(int x){

 return fa[x]==x?fa[x]:fa[x]=fin(fa[x]);

 }

 int unin(int x,int y)

 {

     return fa[fin(y)]=fin(x);

 }

 int main()

 {

    int t,n,a,b;

    cin>>t;

    while(t--){

     cin>>n;

     memset(vis,,sizeof(vis));

     memset(in,,sizeof(in));

     memset(out,,sizeof(out));

     for(int i=;i<;i++){///初始化父亲结点

         fa[i]=i;

     }

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

 scanf("%s",ch);

 a=ch[]-'a';

 b=ch[strlen(ch)-]-'a';

 unin(a,b);///把字符串的开头字母和结尾字母连结起来，即是把它看作是一条有向线段

 out[a]++;///出度

 in[b]++;///入度

 vis[a]=;///标记

 vis[b]=;///标记

 }

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

     fa[i]=fin(i);///fa存储的是每个点最终的根节点

     int cnt=;

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

         if(vis[i]&&fa[i]==i)

             cnt++;

         if(cnt>)///cnt大于1代表除啦根节点，还有根节点没有变的节点，那么此时代表图不连通

         {

             cout<<"The door cannot be opened.\n";

             continue;

         }

         int j=;

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

             if(vis[i]&&out[i]!=in[i])

                 ans[j++]=i;

         }

         if(j==){

             cout<<"Ordering is possible.\n";///j=0代表所有点的入度等于出度，此时形成欧拉回路

             continue;

         }

         if(j==&&((out[ans[]]-in[ans[]]==&&

                    in[ans[j-]]-out[ans[j-]]==)

                   ||out[ans[j-]]-in[ans[j-]]==&&

                   in[ans[]]-out[ans[]]==))///此处为欧拉通路的判断，是初始节点和末尾节点的度的判断，为欧拉通路

         {

             cout<<"Ordering is possible.\n";

             continue;

         }

         cout<<"The door cannot be opened.\n";

    }

 }