杭电 Is It A Tree? 并查集 有向图是否为树

注意 这和上面的题有点不一样 是一个有向图

所以要判断入度

否则会出现

判断成树的情况

#include<stdio.h>
#include<string.h>
#define max 1000+10
int set[max],in[max];//set记录父节点，in记录入度 
int find(int p)
{
    int child=p;
    int t;
    while(p!=set[p])
    p=set[p];
    while(child!=p)
    {
        t=set[child];
        set[child]=p;
        child=t;
    }
    return p;
}
void merge(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
    set[fx]=fy;
}
int main()
{
    int i,j,a,b,exist,t=1,sum,wrong;
    while(1)
    {
        memset(set,0,sizeof(set));
        memset(in,0,sizeof(in)); 
        exist=0;
        while(scanf("%d%d",&a,&b)&&(a!=0||b!=0))
        {
            if(a<0&&b<0)
            return 0;
            if(set[a]==0) set[a]=a;
            if(set[b]==0) set[b]=b;
            in[b]++;
            if(find(a)==find(b)) exist=1;
            merge(a,b);
        }
        if(exist)
        {
            printf("Case %d is not a tree.n",t++);
        }
        else
        {
            sum=0;wrong=0;
            for(i=1;i<max;i++)
            {
                if(set[i]==i)//判断是否连通
                {
                    sum++;
                    if(sum>1)//没有连通 
                    {
                        wrong=1;
                        break;
                    }
                } 
                if(in[i]>1)//入度大于1
                {
                    wrong=1;
                    break;
                } 
            }
            if(wrong)
            printf("Case %d is not a tree.n",t++);
            else
            printf("Case %d is a tree.n",t++);
        }
    }
    return 0;
}