poj 1611_The Suspects_并查集

发布于 2019-04-26  14 次阅读


题目大意

给定很多组人,求出所有和0有关系的人的个数

思路

直接并查集,然后最后判断一下每个点和0的父亲是否一样或是否直接连0就可以了
O(n*m)

#include 
int f[100001];
int find(int x)
{
    if (f[x]==-1) return x;
    f[x]=find(f[x]);
    return(f[x]);
}
int insert(int x,int y)
{
    if(find(x)!=find(y))
    {
        f[find(x)]=find(y);
        return 1;
    }
    return 0;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while (n!=0||m!=0)
    {
        for (int i=0;i<=100000;i++) f[i]=-1;

        for (int i=1;i<=m;i++)
        {
            int x,z;
            scanf("%d%d",&x,&z);
            int y;
            for (int j=2;j<=x;j++)
            {
                scanf("%d",&y);
                insert(find(y),find(z));
            }
        }
        find(0);
        int ans=1;
        for (int i=1;i<=n;i++)
        {
            if (find(i)==f[0]||f[i]==0) ans++;
        }
        printf("%d\n",ans);
        scanf("%d%d",&n,&m);
    }
}
]]>