1272参考答案2

   1 //hdu 1272 并查集
   2 //2009年5月19日19:14:24
   3 //自己做的并查集的第二题，比较麻烦，而且在hdu的判题系统中成功率也很低
   4 //题目描述：小希的迷宫，就是判断输入进的数据是不是一棵树，既没有回路，也没有森林(自己在这里跌了个跟头)
   5 //解决方法：就是并查集搜索，查找根节点，压缩，如果两个数的根节点相同，则说明会产生回路
   6 //比如2->3->4->6,5->6,如果输入2和5，就会造成回路
   7 //特别注意：当输入的是0 0时，结果是Yes
   8 //by  zjd
   9 
  10 
  11 #include <stdio.h>
  12 #include <string>
  13 using namespace std;
  14 
  15 int set[100005];
  16 int used[100005];
  17 int m,n;
  18 int x,y;
  19 int flag;
  20 int tree;
  21 
  22 int  Merge(int x,int y){
  23     used[x]=1;
  24     used[y]=1;
  25     if(x==y)
  26         return 0;        
  27     int xx=x;int x_count=0;
  28     int yy=y;int y_count=0;
  29     while (set[xx]!=-1){  //找出x头结点，并做是否有回路判断
  30         xx=set[xx];
  31     }
  32     while (set[yy]!=-1){//找出y头结点，并做是否有回路判断
  33         yy=set[yy];
  34     }
  35     
  36     int i=x;
  37     int t;
  38     while(set[i]!=-1){    //压缩x
  39         t=set[i];
  40         set[i]=xx;
  41         i=t;
  42     }
  43     int j=y;
  44     while(set[j]!=-1){//压缩y
  45         t=set[j];
  46         set[j]=yy;
  47         j=t;
  48     }
  49     if(xx==yy)
  50         return 0;
  51     else{
  52         set[yy]=xx;
  53     }
  54     return 1;
  55 }
  56 
  57 int main(){    
  58     memset(set,-1,sizeof(set));
  59     memset(used,0,sizeof(used));
  60     flag=1;
  61     tree=0;
  62     while(scanf("%d%d",&x,&y)!=EOF){
  63         if(x==-1&&y==-1)
  64             break;
  65         else if(x==0&&y==0){
  66             for(int ii=0;ii<10005;ii++){
  67                 if(used[ii]==1&&set[ii]==-1){
  68                     tree++;
  69                 }
  70             }
  71             if(flag==0||tree>1)
  72                                 printf("No\n");
  73             else
  74                 printf("Yes\n");
  75             memset(set,-1,sizeof(set));
  76             memset(used,0,sizeof(used));
  77             flag=1;
  78             tree=0;
  79         }
  80         else {
  81             if(Merge(x,y)==0)
  82                 flag=0;
  83                         
  84         }    
  85     }
  86     return 0;
  87 }