本文共 2226 字，大约阅读时间需要 7 分钟。

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

题1：

算法分析：

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

Solving code：

#define _CRT_SECURE_NO_WARNINGS#include 
   
    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;}
   

题二：

算法分析：

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

Solving code：

#define _CRT_SECURE_NO_WARNINGS#include 
   
    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;}
   

题三：

算法分析：

这题比前两天稍微有意思一点，但是也是简单题。我们设定编号为 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 
   
    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;}