HDOJ 1325 并查集

跟小希的迷宫基本一样，只是此题是有向图，要注意：1无环 2 只有一个入度为0的结点（根结点），

不存在入度大于1的结点。输入结束条件是两个负数，而不是-1，不然会TLE。

 1 #include<stdio.h>
 2 #define NUM 23
 3 int root[NUM], visit[NUM], lu[NUM];
 4 void init(){
 5     for(int i=0; i<=NUM; i++){
 6         root[i]=i;
 7         visit[i]=0;
 8         lu[i]=0;
 9     }
10 }
11 int find(int x){
12     while(root[x]!=x)
13         x=root[x];
14     return x;
15 }
16 void merge(int a, int b){
17     int x=find(a);
18     int y=find(b);
19     root[x]=y;
20 }
21 int main(){
22     int a,b,i,flag,count;
23     init();
24     flag = 1;//judge
25     count = 0;//numcase
26     while(EOF != scanf("%d%d",&a,&b)){
27         if(a <0 || b < 0)   break;
28         if(visit[a] == 0)   visit[a] = 1;
29         if(visit[b] == 0)   visit[b] = 1;
30         lu[b]++;
31         //如果是相同的根，会形成环
32         if(find(a) == find(b) && a != 0 && b != 0 && a != b) flag = 0;
33         else    merge(a,b);
34         if(a==0 && b==0){
35             count++;
36             int cnt=0;
37             for(i=1; i<NUM; i++){
38                 if(visit[i] == 1 && root[i] == i)
39                     cnt++;
40                 if(cnt > 1 || lu[i] > 1) //判断是否有2个以上的根 && 不能有入度大于1的点
41                     flag = 0;
42             }
43             if(!flag)
44                 printf("Case %d is not a tree.
",count);
45             else printf("Case %d is a tree.
",count);
46             init();
47             flag=1;
48         }
49     }
50     return 0;
51 }