82 lines
1.9 KiB
C++
82 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 30001;
|
||
int sum[N]; //每个集合人数
|
||
int fa[N]; //并查集数组
|
||
/**
|
||
测试数据
|
||
100 4
|
||
2 1 2
|
||
5 10 13 11 12 14
|
||
2 0 1
|
||
2 99 2
|
||
200 2
|
||
1 5
|
||
5 1 2 3 4 5
|
||
1 0
|
||
0 0
|
||
|
||
答案：
|
||
4
|
||
1
|
||
1
|
||
*/
|
||
|
||
//要深入理解这个递归并压缩的过程
|
||
int find(int x) {
|
||
if (fa[x] != x) fa[x] = find(fa[x]);
|
||
return fa[x];
|
||
}
|
||
|
||
/*
|
||
//查询+带路径压缩(循环版本，非递归)
|
||
int find(int x) {
|
||
int k, j, r;
|
||
r = x;
|
||
while (r != fa[r]) r = fa[r]; //查找跟节点
|
||
//找到跟节点，用r记录下
|
||
k = x;
|
||
while (fa[k] != r) //非递归路径压缩操作
|
||
{
|
||
j = fa[k]; //用j暂存parent[k]的父节点
|
||
fa[k] = r; //parent[x]指向跟节点
|
||
k = j; //k移到父节点
|
||
}
|
||
return r; //返回根节点的值
|
||
}*/
|
||
|
||
//合并并查集
|
||
void join(int a, int b) {
|
||
int x = find(a), y = find(b);
|
||
if (x != y) {
|
||
fa[y] = x;
|
||
//人数合并 路径压缩过程中，也是可以处理附带信息的，并非按秩的就好。
|
||
sum[x] += sum[y];
|
||
}
|
||
}
|
||
|
||
int n, m, K, x, y;
|
||
|
||
int main() {
|
||
while (cin >> n >> m) {
|
||
//输入为 0 0 结束
|
||
if (n == 0 && m == 0) return 0;
|
||
//初始化
|
||
for (int i = 0; i < n; i++) { //因为有0号学生，所以数组遍历从0开始
|
||
fa[i] = i; //每个学生自己是自己的祖先
|
||
sum[i] = 1; //集合中总人数，初始值是1
|
||
}
|
||
for (int i = 0; i < m; i++) {
|
||
cin >> k >> x;
|
||
k--;
|
||
while (k--) {
|
||
cin >> y;
|
||
join(x, y);
|
||
}
|
||
}
|
||
cout << sum[find(0)] << endl; //寻找0号学生相关集合的总人数
|
||
}
|
||
return 0;
|
||
} |