【并查集】ＺＯＪ1789The Suspects

本文主要是介绍【并查集】ＺＯＪ1789The Suspects，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ＺＯＪ1789The Suspects

用简单的并查集水了。。。看到有的题解用的是sum[ra] += sum[rb],这种叫什么名字，不记得了，但是这样肯定比我的好点。

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;int fa[30005];int get_f(int x)
{if(x != fa[x]) fa[x] = get_f(fa[x]);return fa[x];
}int main()
{int n, m;while(scanf("%d%d", &n, &m) != EOF){if(n == 0 && m == 0) break;for(int i = 0; i <= n; i++) fa[i] = i;while(m --){int q, pre = -1;scanf("%d", &q);while(q--){int a;scanf("%d", &a);if(pre == -1){pre = a;continue;}int ra = get_f(pre), rb = get_f(a);if(ra != rb) fa[ra] = rb;}}int x = get_f(0), cnt = 0;for(int i = 0; i < n; i++)if(get_f(i) == x) cnt++;printf("%d\n", cnt);}return 0;
}

这篇关于【并查集】ＺＯＪ1789The Suspects的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---