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.
");

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.
");

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.
");

77                 }else 

78                     printf("The door cannot be opened.
");

79             }

80         }

81     }

82     return 0;

83 }