POJ 1611

菜鸟第一次做这种。想了好一会儿.==

首先还是初始化记忆数组，使得每一个元素的初始根节点是自己。

然后是对输入的数据进行并集。我们拿出每组元素的第一个作为根节点。

每次检测是否已经存在根节点。如果存在根节点压缩该元素通往新的根节点的路径，同时将其原来的根节点接在新的根节点上。

第一次WA是因为忽略了剩余元素的根节点没有更新。倒数第二个循环用于把所有点都连接到根节点上。

#include<stdio.h>

#include<iostream>

using namespace std;

int stu[];

int main()

{

    int n,m,k,tmp1,tmp2,tmp3,er;

    scanf("%d%d",&n,&m);

    while(n)

    {

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

        {

            stu[i]=i;

        }

        for(int i=;i<m;i++)

        {

            scanf("%d",&k);

            scanf("%d",&tmp1);

            for(int j=;j<k-;j++)

            {

                scanf("%d",&tmp2);

                while(stu[tmp2]!=tmp2)

                {

                    tmp3=tmp2;

                    tmp2=stu[tmp2];

                    stu[tmp3]=stu[tmp1];

                }

                stu[tmp2]=stu[tmp1];

            }

        }

        er=;

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

        {

            tmp2=i;

            while(stu[tmp2]!=tmp2)

            {

                tmp2=stu[tmp2];

            }

            stu[i]=tmp2;

        }

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

        {

            if(stu[i]==stu[])

            {

                er++;

            }

        }

        printf("%d\n",er);

        scanf("%d%d",&n,&m);

    }

    return ;

}

巴特西

POJ 1611

最新文章

热门文章