当前位置：首页 > news >正文

个人博客网站开发的意义成人职业培训机构

news 2026/4/6 13:09:01

个人博客网站开发的意义,成人职业培训机构,物流网站制作怎么做,新疆生产建设兵团社保网站目录前言模板朴素实现路径压缩按秩合并按树高为秩按节点数为秩总结前言并查集的基本实现通常使用森林来表示不同的集合，每个集合用一棵树表示，树的每个节点有一个指向其父节点的指针。如果一个节点是它自己的父节点，那么它就是该集合的代…

前言

并查集的基本实现通常使用森林来表示不同的集合，每个集合用一棵树表示，树的每个节点有一个指向其父节点的指针。
如果一个节点是它自己的父节点，那么它就是该集合的代表（称为根节点）。

模板

P3367 【模板】并查集 https://www.luogu.com.cn/problem/P3367

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $N, M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

**样例输入 **

样例输出

N
Y
N
Y

提示

对于 $15\%$ 的数据， $\le 10$ ， $\le 20$ 。

对于 $35\%$ 的数据， $\le 100$ ， $\le 10^3$ 。

对于 $50\%$ 的数据， $1\le N \le 10^4$ ， $1\le M \le 2\times 10^5$ 。

对于 $100\%$ 的数据， $1\le N\le 2\times 10^5$ ， $1\le M\le 10^6$ ， $\le X_i, Y_i \le N$ ， $Z_i \in \{ 1, 2 \}$ 。

朴素实现

code：

# 在集合中查找元素的根节点
def find(x):if x != pre[x]:return find(pre[x])return x# 将两个集合合并为一个集合
def union(x, y, pre):x_root = find(x)y_root = find(y)pre[x_root] = y_rootn, m = map(int, input().split())
pre = [0] * (n + 1)
for i in range(n):pre[i] = i  # 初始化
for _ in range(m):op, x, y = map(int, input().split())if op == 1:union(x, y, pre)else:if find(x) == find(y):print('Y')else:print('N')

在这里插入图片描述

事实证明：我们需要进行时间上的优化

路径压缩

由于在查询过程中只关心根结点是什么，所以我们可以在在集合在查找元素的同时，把集合中所有的元素都直接指向根节点，减少查找的时间

示例code

def find(x):if pre[x] != x:pre[x] = find(pre[x])  # 在回溯时进行路径压缩return pre[x]

tips：可能会破坏原本的结构

按秩合并

之前我们在合并时，是随机合并两个集合
虽然都能得到正确的结果，但存在时间复杂度的差异
怎样降低时间复杂度呢？
通过按秩合并（启发式合并）

“秩”可以理解为树的高度或树的节点数这两种方式
在合并两棵树时，总是把较矮的树挂到较高的树上，节点较小的树挂在节点较多的树上
这种策略有助于保持树的平衡，从而降低查找操作的时间复杂度。

怎么实现？用一个数组记录每个集合的高度或节点数

按树高为秩

示例：

# 将两个集合合并为一个集合
def union(x, y):x_root = find(x)y_root = find(y)if x_root != y_root:# 谁高，谁就作为根节点if rank[x_root] > rank[y_root]:pre[y_root] = x_rootelif rank[x_root] < rank[y_root]:pre[x_root] = y_rootelse:pre[x_root] = y_rootrank[y_root] += 1
# 合并是把小的树直接接到根节点上，所以只有两颗树的高度相等的时候合并后高度才会增加

按节点数为秩

示例：

# 将两个集合合并为一个集合
def union(x, y):x_root = find(x)y_root = find(y)if x_root != y_root:# 谁的节点数多，谁就作为根节点if size[x_root] > size[y_root]:pre[y_root] = x_rootsize[x_root] += size[y_root]else:pre[x_root] = y_rootsize[y_root] += size[x_root]

题解code1（路径压缩+按节点数为秩合并）：

# 在集合中查找元素的根节点
def find(x):global preif pre[x] != x:pre[x] = find(pre[x])  # 在回溯时进行路径压缩return pre[x]# 将两个集合合并为一个集合
def union(x, y):global pre, sizex_root = find(x)y_root = find(y)if x_root != y_root:# 谁的节点数多，谁就作为根节点if size[x_root] > size[y_root]:pre[y_root] = x_rootsize[x_root] += size[y_root]else:pre[x_root] = y_rootsize[y_root] += size[x_root]n, m = map(int, input().split())
pre = list(range(n + 1))  # 初始化pre数组
size = [1] * (n + 1)  # 初始化size数组
for _ in range(m):op, x, y = map(int, input().split())if op == 1:union(x, y)else:if find(x) == find(y):print('Y')else:print('N')

路径压缩与按节点大小合并完全兼容

题解code2（按树高为秩合并）：

# 在集合中查找元素的根节点
def find(x):global preif pre[x] != x:pre[x] = find(pre[x])  # 在回溯时进行路径压缩return pre[x]# 将两个集合合并为一个集合
def union(x, y):global pre, rankx_root = find(x)y_root = find(y)if x_root != y_root:# 谁高，谁就作为根节点if rank[x_root] > rank[y_root]:pre[y_root] = x_rootelif rank[x_root] < rank[y_root]:pre[x_root] = y_rootelse:pre[x_root] = y_rootrank[y_root] += 1
# 合并是把小的树直接接到根节点上，所以只有两颗树的高度相等的时候合并后高度才会增加n, m = map(int, input().split())
pre = list(range(n + 1))  # 初始化pre数组
rank = [1] * (n + 1)  # 初始化rank数组
for _ in range(m):op, x, y = map(int, input().split())if op == 1:union(x, y)else:if find(x) == find(y):print('Y')else:print('N')