当前位置:   article > 正文

并查集(算法)

并查集


一、并查集的概念

最裸并查集:

  1. 将两个集合合并。

  2. 询问两个元素是否在一个集合当中 ,近乎 O ( 1 ) O(1) O(1) 时间内支持两个操作

基本原理:每个集合用一棵树来表示,树根的编号就是整个集合的编号,每个节点存储它的父节点,p[x]表示x的父节点。

  • 如何判断树根?
if (p[x] == x)
  • 1
  • 如何求x的集合编号?
// 暴力遍历
while (p[x] != x) x = p[x];

// 路径压缩优化
int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

此方法要层层遍历父节点来得到根节点 O ( n ) O(n) O(n) n - 树的高度
优化方法:①路径压缩(常用) ②按秩合并 ③启发式合并

  • 如何合并两个集合?
    合并两个集合
// p[x]是x的集合编号,p[y]是y的集合编号
p[x] = y;
  • 1
  • 2

二、并查集的使用

合并集合

题目描述:
一共有 n n n 个数,编号是 1 ∼ n 1∼n 1n,最开始每个数各自在一个集合中。

现在要进行 m m m 个操作,操作共有两种:

  1. M a b,将编号为 a b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
  2. Q a b,询问编号为 ab 的两个数是否在同一个集合中;

输入格式:
第一行输入整数 n n n m m m

接下来 m m m 行,每行包含一个操作指令,指令为 M a bQ a b 中的一种。

输出格式:
对于每个询问指令 Q a b,都要输出一个结果,如果 ab 在同一集合内,则输出 Yes,否则输出 No

每个结果占一行。

数据范围:
1 ≤ n ≤ 1 0 5 1≤n≤10^5 1n105
1 ≤ m ≤ 1 0 5 1≤m≤10^5 1m105

输入样例:

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

输出样例:

Yes
No
Yes
  • 1
  • 2
  • 3

代码实现:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int p[N];

int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
int main()
{
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) p[i] = i;

	while (m--)
	{
		int a, b;
		char op;
		cin >> op >> a >> b;
		switch (op)
		{
		case 'M':
			p[find(a)] = find(b);
			break;
		case 'Q':
			if (find(a) == find(b)) cout << "Yes" << endl;
			else cout << "No" << endl;
			break;
		default:
			cout << "Please enter seriously!" << endl;
			break;
		}
	}
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

连通块中点的数量

题目描述:
给定一个包含 n n n 个点(编号为 1 ∼ n 1∼n 1n)的无向图,初始时图中没有边。

现在要进行 m m m 个操作,操作共有三种:

  • C a b:在点 a a a 和点 b b b 之间连一条边, a a a b b b 可能相等;
  • Q1 a b:询问点 a a a 和点 b b b 是否在同一个连通块中, a a a b b b 可能相等;
  • Q2 a:询问点 a a a 所在连通块中点的数量;

输入格式:
第一行输入整数 n n n m m m。接下来 m m m 行,每行包含一个操作指令,指令为 C a bQ1 a bQ2 a 中的一种。

输出格式:
对于每个询问指令 Q1 a b,如果 a a a b b b 在同一个连通块中,则输出 Yes,否则输出 No

对于每个询问指令 Q2 a,输出一个整数表示点 a a a 所在连通块中点的数量。

每个结果占一行。

数据范围:
1 ≤ n ≤ 1 0 5 1≤n≤10^5 1n105
1 ≤ m ≤ 1 0 5 1≤m≤10^5 1m105

输入样例:

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

输出样例:

Yes
2
3
  • 1
  • 2
  • 3

分析:

并查集 + 附加信息,附加信息为家族中成员的数量,需要一个额外的数组 c n t [ N ] cnt[N] cnt[N]。记录以结点i为根的的家族成员数量。

与最祼并查集的区别:

  • 初始化时,需要将 c n t [ i ] = 1 cnt[i]=1 cnt[i]=1(每次操作为一个点,故初始化为1)

  • 合并时,需要 c n t [ f i n d ( b ) ] + = c n t [ f i n d ( a ) ] cnt[find(b)] += cnt[find(a)] cnt[find(b)]+=cnt[find(a)](利用根节点来计数)

  • 查询时,返回 c n t [ f i n d ( a ) ] cnt[find(a)] cnt[find(a)]


代码实现:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int p[N], cnt[N];
int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
int main()
{
	cin.tie(0);
	int m, n;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) p[i] = i, cnt[i] = 1;

	while (m--)
	{
		int a, b;
		string op;
		cin >> op;
		if (op == "C")
		{
			cin >> a >> b;
			cnt[find(b)] += cnt[find(a)];
			p[find(a)] = find(b);
		}
		else if (op == "Q1")
		{
			cin >> a >> b;
			if (find(a) == find(b)) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
		else if (op == "Q2")
		{
			cin >> a;
			cout << cnt[find(a)] << endl;
		}
		else
			cout << "Please enter seriously!" << endl;
	}

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

食物链

题目描述:
动物王国中有三类动物 A , B , C A,B,C A,B,C,这三类动物的食物链构成了有趣的环形。
A A A B B B B B B C C C C C C A A A

现有 n n n 个动物,以 1 ∼ n 1∼n 1n 编号。

每个动物都是 A , B , C A,B,C A,B,C 中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这 n n n 个动物所构成的食物链关系进行描述:

第一种说法是 1 X Y,表示 X X X Y Y Y 是同类。

第二种说法是 2 X Y,表示 X X X Y Y Y

此人对 n n n 个动物,用上述两种说法,一句接一句地说出 m m m 句话,这 m m m 句话有的是真的,有的是假的。

当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

当前的话与前面的某些真的话冲突,就是假话;
当前的话中 X X X Y Y Y N N N 大,就是假话;
当前的话表示 X X X X X X,就是假话。

你的任务是根据给定的 n n n m m m 句话,输出假话的总数。

输入格式:
第一行是两个整数 n n n m m m,以一个空格分隔。

以下 K K K 行每行是三个正整数 D , X , Y D,X,Y D,X,Y,两数之间用一个空格隔开,其中 D D D 表示说法的种类。

D = 1 D = 1 D=1,则表示 X X X Y Y Y 是同类。

D = 2 D = 2 D=2,则表示 X X X Y Y Y

输出格式:
只有一个整数,表示假话的数目。

数据范围:
1 ≤ n ≤ 50000 1≤n≤50000 1n50000
0 ≤ m ≤ 100000 0≤m≤100000 0m100000

输入样例:

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

输出样例:

3
  • 1

带权并查集

思路:

功能:查询祖先+修改父节点为祖先+更新节点到根的距离(通过到父节点的距离累加和)

d [ i ] d[i] d[i] 的含义:第 i i i 个节点到其父节点距离。

演示


代码实现:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 5e4 + 10;
int p[N], d[N]; // p[]寻找祖宗节点,d[]求到祖宗节点的距离

int find(int x)
{
	if (x != p[x])
	{
		// 路径的长度(高度),是需要自上而下加起来的,从根节点往下走
		// 先触发递归,再从根节点往后增加距离
		int t = find(p[x]); // t暂时存一下p[x]根节点,辅助变量
		d[x] += d[p[x]]; // 更新距离
		p[x] = t;
	}
	return p[x];
}
int main()
{
	cin.tie(0);
	int n, m, res = 0; // res-记录错误数
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) p[i] = i;
	while (m--)
	{
		int t, x, y;
		cin >> t >> x >> y;
		if (x > n || y > n) res++; // 当前话语中x或y比N大,是假话
		else
		{
			int px = find(x), py = find(y); // 查找根节点,每次循环时可以更新节点
			{
				if (t == 1) // 判断是否同类
				{
					// 若 x 与 y 在同一个集合中
					// 两数到根节点距离之差的模不为 0,说明不是同一类,是假话
					if (px == py && (d[x] - d[y] + 3) % 3) res++; // +3来处理负数取模的情况
					else if (px != py) // x 与 y 不在同一个集合中
					{
						p[px] = py;
						d[px] = d[y] - d[x]; // 暂时不更新,下轮循环调用 find 时会更新
					}
				}
				else if (t == 2)
				{
					// 若距离之差 - 1 的模不为 0,说明吃不掉,是假话
					if (px == py && (d[x] - d[y] - 1) % 3) res++;
					else if (px != py)
					{
						p[px] = py;
						d[px] = d[y] - d[x] + 1;
					}
				}
				else cout << "error" << endl;
			}
		}
	}
	cout << res << endl;
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

扩展域并查集

思路:

1 ∼ n 1∼n 1n个元素扩大为 1 ∼ 3 n 1∼3n 13n个元素,使用 [ 1 ∼ 3 n ] [1∼3n] [13n]个并查集(每一个并查集中的所有元素都具有同一种特性,不同并查集中不存在相同元素)来维护3n元素彼此的关系。

为了形象化思考问题,我们假设三种动物,互为食物链: A 、 B 、 C A、B、C ABC关系为:

  • A A A 捕食 B B B
  • B B B 捕食 C C C
  • C C C 捕食 A A A

在这里 x x x元素, x + n x+n x+n元素, x + 2 n x+2n x+2n元素三者的关系被定义为:

  • x x x元素的 p [ x ] p[x] p[x]代表 x x x家族

  • x + n x+n x+n元素的 p [ x + n ] p[x+n] p[x+n]代表 x x x的天敌家族

  • x + 2 n x+2n x+2n元素的 p [ x + 2 n ] p[x+2n] p[x+2n]代表 x x x的猎物家族

对于一句真话:

  • x x x y y y是同类

    • 将他们的天敌集合( x + n x+n x+n y + n y+n y+n所在集合)合并
    • 将猎物集合( x + 2 n x+2n x+2n元素与 y + 2 n y+2n y+2n元素所在集合)合并
    • x , y x,y x,y所在的集合 合并

  • x x x y y y的天敌

    • 将x家族与y的天敌家族合并
    • 将y家族和x的猎物家族合并
    • 将x的天敌家族和y的猎物家族合并

代码实现:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

const int N = 5e4 + 10;
int p[N];

int find(int x)
{
	if (x != p[x]) p[x] = find(p[x]);
	return p[x];
}
void join(int x, int y)
{
	int px = find(x), py = find(y);
	if (px != py) p[px] = py;
}
int main()
{
	cin.tie(0);
	int n, m, res = 0;
	cin >> n >> m;
	for (int i = 1; i <= 3 * n; ++i) p[i] = i;
	while (m--)
	{
		int t, x, y;
		cin >> t >> x >> y;
		if (x > n || y > n) res++;
		else
		{
			if (t == 1)
			{
				if (find(x + n) == find(y) || find(x + 2 * n) == find(y)) res++;
				else
				{
					join(x, y);
					join(x + n, y + n);
					join(x + 2 * n, y + 2 * n);
				}
			}
			else if (t == 2)
			{
				if (find(x) == find(y) || find(x + n) == find(y)) res++;
				else
				{
					join(x + 2 * n, y);
					join(x + n, y + 2 * n);
					join(x, y + n);
				}
			}
			else cout << "error" << endl;
		}
	}
	cout << res << endl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/792332
推荐阅读
相关标签
  

闽ICP备14008679号