链接：

http://poj.org/problem?id=1308

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82830#problem/N

 

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define N 100005int f[N];bool r[N];void IN(){    memset(r, false, sizeof(r));    for(int i=0; i
          
           =0 || b>=0) { if(a==0 && b==0) { if(sum==0) { printf("Case %d is a tree.\n", k++); continue; } int z = Find(MIN); for(i=MIN; i<=MAX; i++) { if(r[i]) { if(z!=Find(i)) // 根（父）节点不同 { flag2=1; break; } } } if(flag1 || flag2) printf("Case %d is not a tree.\n", k++); else printf("Case %d is a tree.\n", k++); IN(); sum=0, flag1=0, flag2=0; } else { sum++; r[a] = 1, r[b] = 1; MIN = min(MIN, min(a ,b)), MAX = (MAX, max(a, b)); fa = Find(a), fb = Find(b); if(fa != fb) f[fa] = fb; else //构成了环 flag1=1; } } return 0;}