poj1308+HOJ1325,判断是否为树

POJ 应该是判断是否为简单无环连通图，用并查集直接秒杀即可，而HOJ的是有向树，还需判断所有点的入度必需小于2，用一个类似hash【】数组判断一下即可，

 ////判断树之一：入度<=1；三：点数-1==边数。用一个集合即可。二：无环，n次均为有效加入

#include<iostream> //判断是否是树  0MS
#include<cstdio>
#include<set>
using namespace std;
int fa[100001];
int mark[100001];   //入度不能大于1
int father(int x){return x==fa[x]?x:father(fa[x]);}
struct edge
{
    int from;
    int to;
};
int main()
{
    int a,b;
    int kcase=1;
    for(int i=0;i<=100000;i++)  
     {
         fa[i]=i;
         mark[i]=0;
     }
     int num=0;  int n=0; int flag=0;
     set<int>se;            //判断树之一：点数-1==边数。用一个集合即可。
    while(~scanf("%d%d",&a,&b)&&a>=0&&b>=0)
    {
        if(a==0&&b==0)
        {

            if(n==0){printf("Case %d is a tree.
",kcase);}
            else
            {
                ////判断树之一：入度<=1；三：点数-1==边数。用一个集合即可。二：无环，n次均为有效加入
                if(flag==0&&n==num&&n==se.size()-1){printf("Case %d is a tree.
",kcase);}
                else{printf("Case %d is not a tree.
",kcase);}
            }
            n=0;num=0;  //初始化。
            kcase++;
            se.clear();
            flag=0;
             for(int i=1;i<=100000;i++)
               {
                   fa[i]=i;
                   mark[i]=0;
               }
        }
        else
        {
            edge temp;temp.from=a;temp.to=b;n++;
            se.insert(a);se.insert(b);
            mark[b]++;              //入度++
            if(mark[b]>1){flag=1;}
           int xx=father(temp.from);int yy=father(temp.to);
           if(xx!=yy)
           {
              fa[xx]=yy;
              num++;
           }
        }
    }
    return 0;
}