2015-07-15

问题简述：

　　给出一组节点关系，判断由这些节点组成的图是否为一颗树。

　　树只有一个根节点，每个节点只有一条边指向它，没有环。

　　原题链接：

解题思路：

　　使用并查集判断是否只有一个根节点是很简单的——让并查集种祖先的父亲是他自己即可方便计算其数量，一旦祖先数量超过一，它就不是树；

　　也可使用并查集判断图是否有环——当两个即将要链接的节点都有相同的祖先时，这就产生了一个环。

源代码：

1 /* 2 OJ: HDOJ 3 ID: forever 4 TASK: 1308.Is It A Tree? 5 LANG: C++ 6 NOTE: 并查集 7 */ 8 #include 
     
       9 10 const int MAX=10005;11 int father[MAX],sign[MAX],flag;12 13 int Find(int x) {14     if(father[x]==x)15         return x;16     else17         return Find(father[x]);18 }19 20 void Union(int x,int y) {21     x=Find(x);22     y=Find(y);23     if(x!=y)24         father[x]=y;25     else26         flag=0;27 }28 29 int main()30 {31     int a,b,k=1;32     while(scanf("%d %d",&a,&b)) {33         if(a==-1&&b==-1) break;34         if(a==0&&b==0) {35             printf("Case %d is a tree.\n",k++);36             continue;37         }38 39         flag=1;40         int m=0;41         for(int i=0;i
      
       m)51                 m=a;52             if(b>m)53                 m=b;54             Union(a,b);55             sign[a]=sign[b]=1;56         }57         int sum=0;58         for(int i=1;i
       
        1) {62                 flag=0;63                 break;64             }65         }66         if(flag)67             printf("Case %d is a tree.\n",k++);68         else69             printf("Case %d is not a tree.\n",k++);70     }71     return 0;72 }