hdu 1272

利用并查集方法，找到各点的根节点。

几点注意：

一、树：1.无环 2.根节点入度为0，其余入度为1

判断依据：

1.若两个点的根节点相同（这两个点是父子关系），则形成环。

2.若所有点中只有一个点的根节点是他本身，则根节点入度为0。

二、

1. 0 0 ：空树也是一颗树。

1 #include
      
        2 #include
       
         3 #define Max 100005 4 using namespace std; 5  6 int f[Max]; 7  8 int root(int i) 9 {10     if(f[i] == i)11         return i;12     else13         return root(f[i]);14 }15 int huan;16 void U(int a,int b)17 {18     int f1,f2;19     f1 = root(a);20     f2 = root(b);21     if(f1 != f2)22     {23         f[f1] = f2;24     }25     else26     {27         huan  = 1;//子环28     }29 }30 int main()31 {32     int n,m,i,j,k,t;33     while(~scanf("%d %d",&n,&m))34     {35         huan = 0;36         memset(f,0,sizeof(f));37         if(m == -1 && n == -1)38             break;39         else if(m == 0 && n == 0)40         {41             printf("Yes\n");42             continue;43         }44         else45         {    46             f[n] = n;47             f[m] = m;48             U(n,m);        49         }50         while(~scanf("%d %d",&n,&m))51         {52             if(n == 0 && m == 0)53                 break;54             else55             {56                 if(f[n] == 0)57                 {58                     f[n] = n; 59                 }60                 if(f[m] == 0)61                 {62                     f[m] = m;63                 }64                 U(n,m);65             }66         }67         if(huan)68         {69             printf("No\n");70             continue;71         }72         k = 0;73         for(i = 0;i < Max;i ++)74         {75             if(f[i] == i && f[i] != 0) //只有一个点的根节点是他本身76                 k ++;77         }78         if(k == 1)79             printf("Yes\n");80         else81             printf("No\n");82     }83     return 0;84 }