hdu 1116(并查集+欧拉路判断）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1116

思路：先合并，然后判断根结点是否唯一，如果是，则在判断是否是欧拉路；否则，直接结束。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=100000+10;
 6 int In[MAXN],Out[MAXN];
 7 int parent[MAXN];
 8 bool mark[MAXN];
 9 int n;
10 
11 
12 void Initiate(){
13     for(int i=0;i<n;i++){
14         parent[i]=-1;
15     }
16 }
17 
18 int Find(int x){
19     int s;
20     for(s=x;parent[s]>=0;s=parent[s]);
21     while(s!=x){
22         int tmp=parent[x];
23         parent[x]=s;
24         x=tmp;
25     }
26     return s;
27 }
28 
29 void Union(int R1,int R2){
30     int r1=Find(R1);
31     int r2=Find(R2);
32     if(r1!=r2){
33         parent[r1]=r2;
34     }
35 }
36 
37 int main(){
38     int _case;
39     scanf("%d",&_case);
40     while(_case--){
41         scanf("%d",&n);
42         Initiate();
43         memset(mark,false,sizeof(mark));
44         memset(In,0,sizeof(In));
45         memset(Out,0,sizeof(Out));
46         for(int i=0;i<n;i++){
47             char str[1010];
48             scanf("%s",str);
49             int x=str[0]-'a';
50             int y=str[strlen(str)-1]-'a';
51             Union(x,y);
52             mark[x]=mark[y]=true;
53             Out[x]++;
54             In[y]++;
55         }
56         int count=0;
57         for(int i=0;i<26;i++){
58             if(mark[i]&&parent[i]==-1){
59                 count++;
60             }
61         }
62         if(count>1){
63             printf("The door cannot be opened.\n");
64         }else {
65             int p[27];
66             int k=0;
67             for(int i=0;i<26;i++){
68                 if(mark[i]&&In[i]!=Out[i]){
69                     p[k++]=i;
70                 }
71             }
72             if(k==0){
73                 printf("Ordering is possible.\n");
74             }else {
75                 if(k==2&&abs(In[p[0]]-Out[p[0]])==1&&abs(In[p[1]]-Out[p[1]])==1){
76                     printf("Ordering is possible.\n");
77                 }else 
78                     printf("The door cannot be opened.\n");
79             }
80         }
81     }
82     return 0;
83 }