并查集

说明

• 并查集是一种精巧使用的数据结构，主要用于处理一些不相交的集合合并问题。经典的例子有连通子图、最小生成树Kruskal算法和LCA等。

原理

• 将编号分别为1~n个对象分为不相交的集合，每个集合中，选择其中某个元素代表所在的集合。在这个集合中，并查集的操作有初始化、合并、找查。

步骤

初始化

• 定义数组int s[]是以结点i为元素的并查集，在开始的时候没处理点与点朋友关系，所以每个点都属于独立的集，并且以元素i的值表示它的集s[i].

//初始化
void init_set(int num[],size_t n)
{
	for (int i = 1; i <= n; i++)
		num[i] = i;
}

合并

• 例如，在并查集s中，把结点1合并到2。

//合并
void union_set(int num[], int x, int y)
{
	x = find_set(num, x);
	y = find_set(num, y);
	if (x != y) num[x] = num[y];	//结点合并

}

找查

• 找查元素是一个递归的过程，知道元素的值和它的集相等就找到了根节点的集。

//找查
int find_set(int num[], int x)
{
	//递归找查，直到元素的值和它的集编号相同为止
	return x == num[x] ? x : find_set(x);
}

统计

• 统计一共有多少个集。

//统计集合个数
int count_union_find(int num[], size_t n)
{
	int ans = 0;
	for (int i = 0; i < n; i++)
		if (num[i] == i)
			ans++;
	return ans;
}

代码

下面以一个问题作为样例

问题(HDU 1213)

									HDU 1213
问题描述
今天是依纳爵的生日。他邀请了很多朋友。现在是晚餐时间。他想知道他至少需要多少张桌子。你要注意的是，并不是所有的朋友都认识对方，所有的朋友都不想和陌生人呆在一起。
这个问题的一个重要规则是，如果我告诉你A知道B，B知道C，这意味着A，B，C彼此认识，所以它们可以留在一个表中。
例如：如果我告诉你A知道B，B知道C，D知道E，那么A，B，C可以留在一个表中，而D，E必须留在另一个表中。所以依纳爵至少需要2张桌子。

输入
输入以整数 T（1<=T<=25） 开头，表示测试用例的数量。然后是 T 测试用例。每个测试用例都以两个整数 N 和 M（1<=N，M<=1000） 开头。N表示好友数，好友从1标记到N。然后是M行。每行由两个整数 A 和 B（A！=B） 组成，这意味着朋友 A 和朋友 B 彼此认识。两个案例之间将有一个空行。

输出
对于每个测试用例，只需输出Ignatius至少需要多少个表。请勿打印任何空白。

示例输入
2
5 3
1 2
2 3
4 5

5 1
2 5

样例输出
2
4

完整代码

#include <iostream>

using namespace std;

//初始化
void init_set(int num[], size_t n)
{
	for (int i = 1; i <= n; i++)
		num[i] = i;
}

//找查
int find_set(int num[], int x)
{
	//递归找查，直到元素的值和它的集编号相同为止
	return x == num[x] ? x : find_set(num, x);
}

//合并
void union_set(int num[], int x, int y)
{
	x = find_set(num, x);
	y = find_set(num, y);
	if (x != y) num[x] = num[y];	//结点合并

}

//统计集合个数
int count_union_find(int num[], size_t n)
{
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (num[i] == i)
			ans++;
	return ans;
}

int main()
{
	int t;
	cin >> t;	//样例组数
	while (t--)
	{
		int num[1024];
		int n, m;	//人数、表示两个人认识的行数
		cin >> n >> m;

		init_set(num, 1024);

		for (int i = 1; i <= m; i++)
		{
			int x, y;
			cin >> x >> y;	//哪两个人认识，即要合并的集合
			union_set(num, x, y);
		}

		cout << count_union_find(num, n) << endl;

	}


	return 0;
}

声明

• 参考《算法竞赛入门到进阶》——清华大学出版社