杭电1272AND北大1308

小希的迷宫

View Code

 1 //杭电1272
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 #define N 100005
 6 int father[N],leftt[N],rightt[N];
 7 int find(int x)
 8 {
 9   if(father[x]==-1)
10       return x;
11   else
12       return find(father[x]);
13 }
14 void unionset(int x,int y)
15 {
16   father[y]=x;
17 }
18 int main()
19 {
20   int a,b;
21   while(scanf("%d%d",&a,&b))
22   {
23     memset(leftt,-1,sizeof(leftt));
24     memset(rightt,-1,sizeof(rightt));
25     memset(father,-1,sizeof(father));
26     if(a==-1&&b==-1)
27         break;
28     if(a==0&&b==0)
29         {printf("Yes\n");continue;}
30     int i=0;
31     leftt[i]=a;rightt[i]=b;
32     while(scanf("%d%d",&a,&b)&&a&&b){
33       i++;
34       leftt[i]=a;rightt[i]=b;
35     }
36     int flag=1;
37     for(int j=0;j<=i;++j)
38     {
39       int p=find(leftt[j]);
40       int q=find(rightt[j]);
41       if(rightt[j]!=find(rightt[j])||p==q)
42       {
43        flag=0;break;
44       }
45       
46         if(p!=q)
47           unionset(p,q);
48      }
49     if(flag==0)
50         printf("No\n");
51     else
52     {
53         int xx=find(rightt[0]),t;
54         for(t=1;t<=i&&xx==find(rightt[t]);++t);
55         if(t>i)
56         printf("Yes\n");
57         else
58             printf("No\n");
59     }
60   }
61   return 0;
62 }

View Code

 1 //北大ｐｏｊ１３０８
 2 
 3 #include<stdio.h>
 4 #include<string.h>
 5 #define N 100005
 6 int a[N],b[N],set[N];
 7 int find(int x)//find函数来查找根结点
 8 {
 9 
10     if(set[x]==-1)
11         return x;
12     else
13         return find(set[x]);//路径压缩，使其递归回来的路径元素都指向其根结点
14 }
15 void power(int x,int y)
16 {
17     set[y]=x;//当两个元素属于同一个集合时，把其合并为同一个集合
18 }
19 int main()
20 {
21     int m,n,i,j,t,l,x,y,f,k;
22     k=0;
23     while(scanf("%d%d",&m,&n))
24     {
25         k++;//用来记忆实例个数
26         memset(a,-1,sizeof(a));
27         memset(b,-1,sizeof(b));
28         memset(set,-1,sizeof(set));//将其根结点全部置为-1
29         if(m==-1&&n==-1)
30             break;
31         if(m==0&&n==0)
32         {
33             printf("Case %d is a tree.\n",k);
34             continue;
35         }
36         i=0;
37         a[i]=m;b[i]=n;
38         while(scanf("%d%d",&m,&n)&&m&&n)
39         {
40             i++;
41             a[i]=m;b[i]=n;//将其每组元素对应存入数组，为下一步更为方便的判断根结点
42         }
43         f=1;
44         for(j=0;j<=i;j++)
45         {
46             x=find(a[j]);
47             y=find(b[j]);
48             if(x==y||b[j]!=y)
49             {
50                 f=0;
51                 break;
52             }
53             else
54             {
55                 if(x!=y)
56                     power(x,y);
57             }
58         }
59         if(f==0)
60 
61             printf("Case %d is not a tree.\n",k);
62             
63 
64         else
65         {
66             l=find(b[0]);
67         
68             for(t=1;t<=i&&l==find(b[t]);++t);
69             if(i<t)
70                 printf("Case %d is a tree.\n",k);
71             else
72                 printf("Case %d is not a tree.\n",k);
73         }
74     }
75     return 0;
76 }
77

本道题主要运用查并集，主要难点在于如何对无序的元素集合关系进行根结点判断。代码从网上找的，到现在也不是很明白。