并查集-POJ 1611-The Suspects

左手的ㄟ右手 2022-05-15 01:58 157阅读 0赞

*  # 并查集-POJ 1611-The Suspects #

--------------------

*  ## 题目链接：[The Suspects][] ##
 *  ## 并查集基础： ##

### [数据结构-并查集][-] ###

*  ## 思路： ##

### 题目大意： ###

0号同学是非典可疑患者，需要把和他可能有接触的群体隔离起来，问得隔离多少人

### 题解： ###

**只要0所在群体的其他人有在另一个群体，那么那个群体也会被隔离，用并查集找出0所在的集合**

然后只要计数就可以啦，看看多少人和0在一个集合

*  ## 代码： ##

#include<iostream>
    using namespace std;
    #define MAX_SIZE 30005
    int Student[MAX_SIZE];
    
    void Init(int n)
    {
        for(int i=0;i<n;i++)
            Student[i]=-1;
    }
    
    int Find(int Index)
    {
        if(Student[Index]==-1)
            return Index;
        else
            return Find(Student[Index]);
    }
    
    void Combine(int a,int b)
    {
        int a_root=Find(a);
        int b_root=Find(b);
        if(a_root!=b_root)     //创建集合
            Student[a_root]=b_root;
    }
    
    int main()
    {
        int n,m,k;
        while(cin>>n>>m)
        {
            if(n==0&&m==0)
                break;
            Init(n);
            while(m--)
            {
                cin>>k;
                int a,b;
                for(int i=0;i<k;i++)
                {
                    if(i==0)
                        cin>>a;
                    else
                    {
                        cin>>b;
                        Combine(a,b);
                        a=b;
                    }
                }
            }
            int Root_0=Find(0);   //0所在集合
            int Res=0;
            for(int i=0;i<n;i++)   //计数
            {
                if(Find(i)==Root_0)
                Res++;
            }
            cout<<Res<<endl;
        }
        return 0;
    }

[The Suspects]: http://poj.org/problem?id=1611
[-]: https://blog.csdn.net/SZU_Crayon/article/details/81986258