并查集

2022/4/3 23:24:07

本文主要是介绍并查集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

并查集

说明

  • 并查集是一种精巧使用的数据结构,主要用于处理一些不相交的集合合并问题。经典的例子有连通子图、最小生成树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;
}

声明

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


这篇关于并查集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程