并查集
说明
- 并查集是一种精巧使用的数据结构，主要用于处理一些不相交的集合合并问题。经典的例子有连通子图、最小生成树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;
}
声明
- 参考《算法竞赛入门到进阶》——清华大学出版社
