hdu 1116 并查集判断欧拉回路通路

判断一些字符串能首尾相连连在一起

并查集求欧拉回路和通路

Sample Input

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

Sample Output

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 typedef long long ll;
13 #define cl(a) memset(a,0,sizeof(a))
14 #define ts printf("*****
");
15 const int MAXN=1005;
16 int n,m,tt;
17 char s[MAXN];
18 int in[27],out[27],vis[27],f[27],p[27];
19 int find(int x)
20 {
21     if(f[x]==-1)return x;
22     return f[x]=find(f[x]);
23 }
24 void bing(int x,int y)
25 {
26     int t1=find(x);
27     int t2=find(y);
28     if(t1!=t2)
29     {
30         f[t1]=t2;
31     }
32 }
33 void init()
34 {
35     cl(vis);
36     cl(in);
37     cl(out);
38     memset(f,-1,sizeof(f));
39 }
40 int main()
41 {
42     int i,j,k;
43     #ifndef ONLINE_JUDGE
44     freopen("1.in","r",stdin);
45     #endif
46     scanf("%d",&tt);
47     while(tt--)
48     {
49         init();
50         scanf("%d",&n);
51         for(i=0;i<n;i++)
52         {
53             scanf("%s",s);
54             int len=strlen(s);
55             int x=s[0]-'a';
56             int y=s[len-1]-'a';
57             out[x]++;
58             in[y]++;
59             bing(x,y);
60             vis[x]=vis[y]=1;
61         }
62         int cnt=0;  //统计个数
63         for(i=0;i<26;i++)
64         {
65             if(vis[i]&&find(i)==i)
66             {
67                 cnt++;
68             }
69         }
70         if(cnt>1)
71         {
72             printf("The door cannot be opened.
");
73             continue;
74         }
75         int tot=0;  //统计出入度不相同的点
76         for(i=0;i<26;i++)
77         {
78             if(vis[i]&&in[i]!=out[i])
79             {
80                 p[tot++]=i;
81             }
82         }
83         if(tot==0)
84         {
85             printf("Ordering is possible.
");
86             continue;
87         }
88         if(tot==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))) //欧拉通路
89         {
90             printf("Ordering is possible.
");
91             continue;
92         }
93         printf("The door cannot be opened.
");
94     }
95 }