B - The Suspects

这个题是并查集的应用,如何找到可能的患者?我们只需要把和患者(编号0)会牵扯到一起有关联的社团全都加在一个父节点下面就行了,虽然使用了路径压缩算法,但是最后还是可能会存在树高为3的树,所以这里的路径压缩并不彻底,AC的时间比大部分高,还有待优化(其实优化过一次,不过是错的)。


#include <iostream>
//#include <cstdio>
using namespace std;
const int maxn=30000;
int n, m, num, master, people;
int studata[maxn];
void Init()
{
    ///初始化上级为自己
    for(int i=0;i<n;i++)studata[i]=i;
}
int Find(int man)
{
    ///找父级并且压缩路径
    int fmaster=man;
    while(studata[fmaster]!=fmaster)fmaster=studata[fmaster];
    int fman=man, tman;
    while(studata[fman]!=fmaster)
    {
        tman=studata[fman];
        studata[fman]=fmaster;
        fman=tman;
    }
    return fmaster;
}
int Find2(int man)
{
    ///单独找父级
    int fmaster=man;
    while(studata[fmaster]!=fmaster)fmaster=studata[fmaster];
    return fmaster;
}
void Join(int remaster, int repeople)
{
    ///加入节点
    int jmaster=Find(remaster);
    int jpeople=Find(repeople);
    if(jmaster!=jpeople)
    {
        studata[jpeople]=jmaster;
    }
}

void Print2()
{
    int pmaster=Find2(0);
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(Find(studata[i])==pmaster)ans++;
        //cout<<"<"<<i<<","<<Find(studata[i])<<">  ";
    }
    cout<<ans<<endl;
}
int main()
{
    while(cin>>n>>m && n+m)
    {
        Init();
        while(m--)
        {
            cin>>num>>master;
            for(int i=0;i<num-1;i++)
            {
                cin>>people;
                Join(master, people);
            }
        }
        Print2();
    }
    return 0;
}