题解 - The Suspects

· · 题解

这题是一个纯并查集题

从“如果一个群体中有一个人是非典患者，那么这个群体中的所有人都是非典患者。”这句话可以简化成有多个集合，求与0在同一个集合里的所有人数

先给个find函数路径压缩

int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

对并查集不熟的小伙伴可以百度一下，这里推荐一个，本人认为讲的很不错

并查集

一个群体中的合并操作

if(find(x)!=find(y)) f[f[x]]=f[y];//如果x与y不在同一集合中，将祖先和祖先合并即可使两集合合并

直接上代码

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int f[30050];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);//路径压缩
}
int main()
{
    while(1)
    {   
        int n,m;
        cin>>n>>m;
        if(n==0&&m==0) break;
        for(int i=0;i<n;i++)
            f[i]=i;             //先全部初始化为自己，即为自己就是一个集合
        for(int i=1;i<=m;i++)
        {
            int num;cin>>num;   //人数
            int x;cin>>x;       //先输第一个数，方便合并
            for(int j=2;j<=num;j++)
            {
                int y;cin>>y;
                if(find(x)!=find(y)) f[f[x]]=f[y];//第一个和后面输入的挨个合并
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
            if(find(0)==find(i)) ans++; //如果查找0的祖先是某个编号的祖先时，说明这个人会被0感染，计数器+1
        cout<<ans<<endl;    //输出会被感染的人数
    }
    return 0;
}