poj1611(带权并查集)

题意：

有ｎ个学生，ｍ个组，每个学生可能属于多个组，现在０号得了ＳＡＲＳ；

和０号一组的也会得，然后和０号一组的人，他所在的组的组员也全会得，问最后总共几个人得了ＳＡＲＳ；

思路：

只要加一个权值，就是这个组有多少个人；如r[i]表示ｉ所在的组有多少人；

所以每次并的时候，也要把这个组的人数并过去；

最后数组０所在的组有几个人；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 30000 + 10;
int p[N], r[N], n, m;
void init(int x) {
	for(int i = 0; i <= x; i++) {
		r[i] = 1;
		p[i] = i;
	}
}
int find_p(int x) {
	return x == p[x] ? x : p[x] = find_p(p[x]);
}

void Union(int x,int y) {
	int px = find_p(x);
	int py = find_p(y);
	if(px != py) {
		p[px] = py;
		r[py] += r[px];
	}
}
int main() {
	int k,f;
	while(scanf("%d%d",&n,&m) && (n + m)) {
		init(n);
		for(int i = 0; i < m; i++) {
			scanf("%d",&k);
			scanf("%d",&f);
			int tmp;
			for(int j = 0; j < k - 1; j++) {
				scanf("%d",&tmp);
				Union(f,tmp);
			}
		}
		int ans = find_p(0);
		printf("%dn",r[ans]);
	}
}

最后

以上就是唠叨彩虹为你收集整理的poj1611(带权并查集)的全部内容，希望文章能够帮你解决poj1611(带权并查集)所遇到的程序开发问题。

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