The Suspects （并查集）

题目大意：多个块，如果一个块里有0，则这个块里所有人都是患者，如果里边的患者又在其他块里，那么另外一个块里的也都是患者，以此类推；

题解：很明显的并查集，用num[]数组记录之间的关系，先将num数组初始化为1，之后如果a和b之间有关系，将num[a]加到num[b]上，就相当于知道了多一个人是患者。这样每个点的记录数都是不一样的。

其他都是按模板，Union函数稍微改一下。

完整代码：

#include <iostream>
#include <stdlib.h>
using namespace std;
#define MAX1 33000
int N,M;
int pre[MAX1];
int num[MAX1];
void  Init()
{
    for(int i=0;i<N;i++)
    {
        pre[i]=i;
        num[i]=1;
    }
}
int find(int x)
{
    int r=x;
    while(pre[r]!=r)
        r=pre[r];
    return r;
}
void Union(int x,int y)
{
    int a;int b;
    a=find(x);
    b=find(y);
    if(a!=b)
       {
            pre[a]=b;
            num[b]+=num[a];
       }
}
int main()
{
    int k;
    int a[MAX1];
    while(cin>>N>>M,N||M)
    {
        Init();//刚开始忘了写这个，所以一直输出0；
        while(M--)
           {
               cin>>k;
               for(int j=0;j<k;j++)
                cin>>a[j];
               for(int i=0;i<k-1;i++)
                Union(a[i],a[i+1]);
           }
    int k=find(0);
    cout<<num[k]<<endl;
    }
    return 0;
}

最后

以上就是健忘豌豆为你收集整理的The Suspects （并查集）的全部内容，希望文章能够帮你解决The Suspects （并查集）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。