HDU1325

http://acm.split.hdu.edu.cn/showproblem.php?pid=1325

#include<stdio.h>

 #include<algorithm>

 #include<string.h>

 #include<iostream>

 using namespace std;

 const int M=;

 int fa[M],vis[M],root[M];

 int fin(int x){

 return fa[x]==x?fa[x]:fa[x]=fin(fa[x]);

 }

 int  unin(int x,int y){

 return fa[fin(y)]=fin(x);

 }

 void init(int n){

 for(int i=;i<n;i++){

     fa[i]=i;

 }

 memset(vis,,sizeof(vis));

 memset(root,,sizeof(root));

 }

 int main()

 {

     int a,b;

     int cas=;int flag=;

     init(M);

     while(~scanf("%d%d",&a,&b)){

         if(a<||b<)break;

         if(a==&&b==){

             int k=;

             for(int i=;i<M;i++){

                 if(vis[i]&&fa[i]==i){

                     k++;

                 }

                 if(root[i]>){

                     flag=;

                     break;

                 }

             }

             if(k>)flag=;

             if(flag)printf("Case %d is a tree.\n",cas++);

             else printf("Case %d is not a tree.\n",cas++);

             flag=;

             init(M);

             continue;

         }

         if(a!=b&&fin(a)==fin(b)){

             flag=;

         }

         else {

             vis[a]=;

             vis[b]=;

             root[b]++;

             unin(a,b);

         }

     }

     return ;

 }

对于这道题，主要是看图是否连通，而前面提到过在分析图是否连通的时候我们主要是看有几个根结点，而看有几个根节点又是看有几个fa[i]==i。
至于题目中说到的值可以有一种方法到达每一个节点，则是要看每个节点的入度情况，当出现有一个节点的入度大于1的话肯定就是NO

还可以发现，结点数一定小于边数-1，然后再判断有几个根结点也可以解出这道题，但是我们在这里主要运用并查集的知识