The Suspects 并查集练习

题目地址： https://vjudge.net/problem/POJ-1611

题目大意：最近SARS传播， 学校里为了隔离可能被感染的人， 让你找出个能被感染的人， 现规定， 在同一个社团中， 只要有一人有感染嫌疑， 则所有人都有感染嫌疑， 已知0号学生是感染嫌疑者，现在给你学校里有n个学生， m个社团，输入第一行是n 和 m， 之后的m行， 先给出这个社团的成员人数， 再给出成员的学号。

解题思路：把社团里的成员都并到这个这团的第一个人身上， 如果社团中有0，就把第一个并到0上。（有点麻烦， 毕竟我还是萌新）

ac代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;

const int MAX = 30010;
int stu[MAX];
int n, m, ans;

void makeset(int n)
{
      for(int i = 0; i < n;i++)
            stu[i] = i;
}

int finding(int x)
{
      if(x != stu[x]) stu[x] = finding(stu[x]);
      return stu[x];
}

void bing(int x, int y)
{
      if(finding(x) != finding(y))
            stu[finding(x)] = finding(y);
}
int main()
{
      int a, b, first, out;
      while(scanf("%d%d", &n, &m) != EOF)
      {
            makeset(n);
            out = 0;
            if(n == 0 && m == 0) break;
            if(n == 1 && m == 0)
            {
                  cout << 1 << endl;
                  continue;
            }
            while(m--)
            {
                  cin >> a >> first;
                  for(int i = 0; i < a - 1; i++)
                  {
                        cin >> b;
                        if(b == 0) stu[finding(first)] = b;
                        else if(finding(first) != 0 && finding(b) != 0) bing(first, b);
                        else if(finding(first) == 0) stu[finding(b)] = finding(first);
                        else if(finding(b) == 0) stu[finding(first)] = finding(b);
                  }
            }
            for(int i = 0 ; i < n; i++)
            {
                  if(finding(stu[i]) == 0) {out++;}
            }
            cout << out << endl;
      }

    return 0;
}

最后

以上就是魔幻冰棍为你收集整理的The Suspects 并查集练习的全部内容，希望文章能够帮你解决The Suspects 并查集练习所遇到的程序开发问题。

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