并查集训练1：基础并查集

题1：也可在HDOJ 1213提交

算法分析：

这题就是数朋友圈的数目，可以用并查集或者DFS，说明并查集可以用于计算联通块的数目。只需要把是朋友的并在一起，选取一个作为代表，然后去数有多少个代表就是有多少个圈子。

Solving code：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

const int maxn = 1005;
int t, n, m, p[maxn];

int find(int x) {
	if (x == p[x])
		return x;
	return p[x] = find(p[x]);
}

void merge(int x, int y) {
	int px = find(x), py = find(y);
	if (px != py)
		p[py] = px;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", & n, &m);
		for (int i = 1; i <= n; i++)
			p[i] = i;
		int ans = 0;
		for (int i = 0; i < m; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			merge(a, b);
		}
		for (int i = 1; i <= n; i++) {
			if (i == p[i])
				ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

题二：POJ 2524 有多少种宗教被人信仰

算法分析：

这题的算法和上一题是一样的，完全一样，就是同一信仰的人被合并到一起，去数有多少种信仰就可以了！

Solving code：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

const int maxn = 5e4 + 5;
int kcase, n, m, p[maxn];

int find(int x) {
	if (x == p[x])
		return x;
	return p[x] = find(p[x]);
}

void merge(int x, int y) {
	int px = find(x), py = find(y);
	if (px != py)
		p[py] = px;
}

int main() {
	while (scanf("%d %d", &n, &m) && (n || m)) {
		kcase++;
		for (int i = 1; i <= n; i++)
			p[i] = i;
		int ans = 0;
		for (int i = 0; i < m; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			merge(a, b);
		}
		for (int i = 1; i <= n; i++)
			if (i == p[i])
				ans++;
		printf("Case %d: %d\n", kcase, ans);
	}
	return 0;
}

题三：POJ 1611 有多少嫌疑人

算法分析：

这题比前两天稍微有意思一点，但是也是简单题。我们设定编号为 0 的是嫌疑人，和 0 一组的都是嫌疑人，问有多少个嫌疑人。那样我们可以每组并在一起，以为我们并不一定是以0 为 0所在组的代表，所以我们做最后统计的时候，万万不可以：if(!p[i]) ans++;这样是绝对错误的！因为我们的 0 可能最后的p[0] != 0，所以我们应该要去搜索 i 所在的组，是不是与 0 同组：if(find(i) == p[0]) ans++;

Solving code:

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

const int maxn = 5e4 + 5;
int n, m, p[maxn];

int find(int x) {
	if (x == p[x])
		return x;
	return p[x] = find(p[x]);
}

void merge(int x, int y) {
	int px = find(x), py = find(y);
	if (px != py)
		p[py] = px;
}

int main() {
	while (scanf("%d %d", &n, &m) && (n || m)) {
		for (int i = 0; i < n; i++)
			p[i] = i;
		int ans = 0;
		for (int i = 0; i < m; i++) {
			int k, a, b;
			scanf("%d", &k);
			if (k--)	scanf("%d", &a);
			while (k--) {
				scanf("%d", &b);
				merge(a, b);
			}
		}
		for (int i = 0; i < n; i++)
			if (find(i) == p[0])
				ans++;
		printf("%d\n", ans);
	}
	return 0;
}