并查集
目录定义
并查集(Disjoint-Set)是一种可以动态维护若干个不重叠的集合,并支持合并与查询两种操作的一种数据结构。
模板题目
原题链接
题目描述
一共有 \(n\) 个数,编号是 \(1∼n\),最开始每个数各自在一个集合中。
现在要进行 \(m\) 个操作,操作共有两种:
M a b
,将编号为 \(a\) 和 \(b\) 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;Q a b
,询问编号为 \(a\) 和 \(b\) 的两个数是否在同一个集合中;
输入格式
第一行输入整数 \(n\) 和 \(m\)。
接下来 \(m\) 行,每行包含一个操作指令,指令为 M a b
或 Q a b
中的一种。
输出格式
对于每个询问指令 Q a b
,都要输出一个结果,如果 \(a\) 和 \(b\) 在同一集合内,则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
$ 1 \le n,m \le 10^5 $
分析
这是一道并查集模板题
并查集
- 将两个集合合并;
- 询问两个元素是否在一个集合当中。
时间复杂度近乎 \(O(1)\)。
基本原理
每个集合用一颗树来表示。
树根的编号就是整个集合的编号。
每个节点存储他的父节点, \(p_x\) 表示 \(x\) 的父节点。
实现步骤
问题1
如何判断树根?
answer: if(p[x]==x);
即 根节点存储自己。
问题2
如何求x的集合编号?
answer: while(p[x]!=x) x=p[x];
即 顺着父节点找到根节点。
问题3
如何合并两个集合?
answer:
\(px\) 是 \(x\) 集合编号,\(py\) 是 \(y\) 的集合编号。p[x]=py;
即 将 \(y\) 所在集合的根节点作为 \(x\) 所在集合的根节点的父节点
优化
使用路径压缩进行优化
即 在求 \(x\) 的根节点时,直接将一路上 \(p_x\) 的值赋成根节点的值
使用递归实现:
点击查看代码
int find(int x) // 查找x的根节点,采用递归实现路径压缩
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
代码实现
Code:
#include <iostream>
using namespace std;
const int N = 1e5+5;
int p[N];
int find(int x) // 查找x的根节点,采用递归实现路径压缩
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
// 初始化——每一个都为根节点(根节点表示一个集合)
for (int i = 1; i <= n; ++ i)
p[i] = i;
while (m -- )
{
char op;
int a, b;
scanf(" %c%d%d", &op, &a, &b); // scanf(" %c", &c)在%c之前空格会告诉scanf忽略前面的空行,而等待第一个非空行元素读入其中
if (op == 'M')
p[find(a)] = find(b); // 将b所在集合的根节点作为a所在集合的根节点的father
else
{
if (find(a) == find(b)) // 根节点相同说明a与b在同一个集合
puts("Yes");
else
puts("No");
}
}
return 0;
}
标签:Set,int,查集,find,集合,编号,Disjoint,节点
From: https://www.cnblogs.com/MingruiYang/p/17063832.html