POJ1308/HDU1325/NYOJ129-Is It A Tree?，并查集！

Is It A Tree?

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 28838		Accepted: 9843

-> Link poj <-

-> Link
hdu<-

-> Link
NYoj <-

这三个题题目都是一样的，我先做的NYOJ上的，以-1、-1结尾，然后跑到HDu上交一遍跪了，改成同时小于0就A了，又到POJ上交一遍又跪了，改成-1、-1结尾又A了；

题意：给你一些点对x,y，每组以0 0结尾，最后以-1、-1或一对负数结束，y表示被指向的点；也就是说两点之间是一条单向边；然后给出树的定义，判断是否为合法树：

There is exactly one node, called the root, to which no directed edges point. //只有一个根节点（无被指向的边,入度为0）；

Every node except the root has exactly one edge pointing to it. //入度为1

There is a unique sequence of directed edges from the root to each node. //无环也就是路径唯一，这里和小希的迷宫那题有点类似；

思路：典型并查集题，既然给出了这三个条件，那么我们就从这条件出发；用一个vis[]数组来存入度（被指向的节点入度++，即vis[y]++），所有节点的入度都小于2（这里知道怎么判断了吧）；那么怎么判断路径唯一呢，我们可以发现，如果入度大于等于2或者指向自己都是会成环的，所以在合并的时候判断两节点是否联通，若已经联通这条边必然无用（这里也判断一下）；最后我们找是否只有一个根节点，注意除根节点外合法树其他点入度都为1，所以我们遍历一遍所有的点看其入度情况；

几个特殊样例注意一下：

0 0代表空树，也是合法的；

1 1 0 0不合法，自己指向自己；

注意如果不连通不合法；

using namespace std;

const int N=100000+10;

int v[N],f[N],a[N];//v[]用来存节点入度，a[]用来存点；

int find(int x)

{

    return f[x]==-1?x:f[x]=find(f[x]);

}

int main()

{

    int x,y,i=0,t=1;

    while(~scanf("%d%d",&x,&y)&&x!=-1&&y!=-1)//HDu这里只需改成同时小于0就行；

    {

        if(x==0&&y==0)//空树；

        {

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

            continue;

        }

        int ff=0,k=0;

        memset(f,-1,sizeof(f));

        memset(a,0,sizeof(a));

        memset(v,0,sizeof(v));

        int xx=find(x);

        int yy=find(y);

        if(xx!=yy)

            f[xx]=yy;

        else

            ff=1;

        a[k++]=x,a[k++]=y;//存点；

        v[y]++;

        for(i=1;; i++)

        {

            scanf("%d%d",&x,&y);

            if(x==0&&y==0) break;

            int xx=find(x);

            int yy=find(y);

            if(xx!=yy)

                f[xx]=yy;

            else

                ff=1;//自己指向自己或有多条路到达某个点；

            a[k++]=x,a[k++]=y;

            v[y]++;

            if(v[y]>1) ff=1;//除根节点每个节点只有一条被指向边,入度为1；

        }

       if(ff) printf("Case %d is not a tree.\n",t++);

       else

       {

           sort(a,a+k);

           int kk=unique(a,a+k)-a;//不同的点；

           for(i=0;i<kk;i++)//数组a[]的作用在于此；

           if(v[a[i]]!=1)//判断入度不为1的点有几个，合法树只有根节点不为1；

            ff++;

           if(ff!=1)

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

           else

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

       }

    }

   return 0;

}

巴特西

POJ1308/HDU1325/NYOJ129-Is It A Tree?，并查集！

最新文章

热门文章