poj1611 The Suspects 并查集
标签:并查集
题目链接
/*
题意:n个学生(0~n-1),m组,一个学生可以同时加入不同的组。
有一种传染病,如果一个学生被感染,那么和他同组的学生都会被感染。
现已知0号学生被感染,问一共有多少个人被感染。
思路:基本的并查集操作。
首先将每个学生都初始化为一个集合,然后将同组的学生合并,
设置一个数组num[]来记录每个集合中元素的个数,最后只要输出0号学生所在集合中元素的个数即可。
*/
#include <stdio.h>
int num[30005]; //结点所在集合元素的个数
int father[30005];
void make_set(int x){ //初始化集合
father[x] = x;
num[x] = 1;
}
int find_set(int x){ //查找x元素所在集合, 返回根节点
return x == father[x] ? father[x] : find_set(father[x]);
}
void union_(int x, int y){ //合并x, y所在的集合
x = find_set(x), y = find_set(y);
if(x == y) return ; //同一个集合则不需要合并
if(num[x] < num[y]) { //小集合合并到大集合
father[x] = y;
num[y] += num[x];
}
else{
father[y] = x;
num[x] += num[y];
}
}
int main(){
int n, m, t, x, y, i, j;
while(scanf("%d %d", &n, &m) && (n || m)){
for(i = 0; i < n; i++) make_set(i);
for(i = 0; i < m; i++){
scanf("%d", &t);
scanf("%d", &x);
for(j = 1; j < t; j++){
scanf("%d", &y);
union_(x, y);
}
}
printf("%dn", num[find_set(0)]);
}
return 0;
}
最后
以上就是活力舞蹈最近收集整理的关于poj1611 The Suspects 并查集poj1611 The Suspects 并查集的全部内容,更多相关poj1611内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复