并查集详解与实战

了解并参与社区的应急演练，增强实战经验。 #生活技巧# #紧急应对技巧# #公共安全演练#

并查集速讲

视频连接!

简介

并查集是一种很简单的数据结构。
它的作用是快速的维护查找一个集合。
每次我们用p[x]表示当前点的父节点。
x表示当前点的树根。
这样我们就可以查找访问集合了。

并查集的思路

我们首先画出一颗树。
接着我们想一下如何找到这个点所在的集合是什么。
其实非常简单，我们可以不停的判断：

if(p[x] != x) 1

如果这样就说明这个点不是树根，那就继续往上走。

find(p[x]); 1 并查集的优化——路径压缩

如果我们这样，一个点历经千辛万苦终于找到了它的根节点。
那如果我们在查找这个点它就又需要重新千辛万苦的走一遍。
玩游戏的人肯定问了：凭啥不开个传送点啊。
那我们就可以实施所谓的升维大法（来源于“降维打击”），
把所有走过的点直接指向根节点。
这就叫做：如果你费劲千辛万苦，走到的是根节点，
如果你开VIP传送过去，到的还是根节点。
那这个VIP叫神马呢？
请看小标题：路径压缩

接下来就是所谓的并查集版“西游记”。
费劲千辛万苦，打败了魑魅魍魉，最后找到了根节点（不是真经！）。

int find(int x) {if(p[x] != x) p[x] = find(p[x]);//路径压缩DLCVIPreturn p[x]; } 12345 并查集的初始化

其实就是让每个点指向自己的自己吗。
让每个点单独独立出来。
那我们遍历一遍整个数组就好了。

for(int i = 1; i <= n; i ++) {p[i] = i; } 1234 我们来康康题。 合并集合连通块中点的数量银河英雄传说 1、合并集合

题目：
一共有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≤n,m≤105 1

输入样例：

4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4 123456

输出样例：

Yes No Yes 123

我们想一下如何合并两个集合（见下）
我们可以在两个集合里建一条边，让其中一个集合的根节点指向另一个集合的根节点。

p[find(a)] = find(b); 1

那查询就 再简单不过了对吧。

if(find(a) == find(b)) puts("Yes"); else puts("No"); 12 完整代码：

#include<iostream> using namespace std; const int N = 1e5 + 10; int n, m, p[N]; int find(int x) { if(p[x] != x) p[x] = find(p[x]); return p[x]; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) p[i] = i; while(m --) { int a, b; char op; cin >> op; scanf("%d%d", &a, &b); if(op == 'M') p[find(a)] = find(b); else { if(find(a) == find(b)) puts("Yes"); else cout << "No" << endl; } } return 0; }

12345678910111213141516171819202122232425262728 2、连通块中点的数量

题目：
给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。

现在要进行m个操作，操作共有三种：

“C a b”，在点a和点b之间连一条边，a和b可能相等；
“Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；
“Q2 a”，询问点a所在连通块中点的数量；
输入格式
第一行输入整数n和m。

接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。

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

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

每个结果占一行。

数据范围

1≤n,m≤105 1

输入样例：

5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5 123456

输出样例：

Yes 2 3 123

这道题需要单独定义一个cnt数组来存点的数量。
先说下弱的不行的Q1操作和Q2操作
Q1：同上道题。

if(find(a) == find(b)) puts("Yes"); else puts("No"); 12

Q2：直接输出就行了。

cout << cnt(find(a)) << endl; 1

然后是建立边的操作。
我们建立一条边要做两件事：
1、建立边，要把边建立出来。

p[find(a)] = find(b); 1

2、把a连通块的点数加进b连通块

cnt[find(b)] += cnt[find(a)]; 1

本题完整代码：

#include<iostream> using namespace std; const int N = 1e5 + 10; int n, m, p[N], cnt[N]; int find(int x) { if(p[x] != x) p[x] = find(p[x]); return p[x]; } int main() { 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; int pa = find(a), pb = find(b); if(pa != pb) { p[pa] = pb; cnt[pb] += cnt[pa]; } } else if(op == "Q1") { cin >> a >> b; if(find(a) == find(b)) puts("Yes"); else puts("No"); } else{ cin >> a; cout << cnt[find(a)] << endl; } } return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445

好作业大家看看就行了。
有点难，有时间下节课讲解哦！
作业上面其实已经说过了，再说一遍。
算法竞赛进阶指南0x40数据结构进阶并查集第2题：银河英雄传说（链接上面有）

今天的分享就到这里了。

未经允许，请勿转载！

这是我的全部分享

关于acwing

bye~

网址：并查集详解与实战 https://www.yuejiaxmz.com/news/view/898483

相关内容

《图表详解小家电维修实战》
全面战争三国全DLC内容详解
3月处女座运势全解：机遇与挑战并存！
家务游戏实用攻略与步骤详解
如何撰写有效的优化方案：详细指南与实例解析
压力测试问卷调查及答案详解图，压力测试问卷调查及答案详解
四、套件包详解：灰尘大作战
深圳到广州汽车票价详解：实时查询与优惠策略一览
AI助手时代：挑战与机遇并存
大模型微调与部署：实战技巧与类GPT工具高效应用

随便看看