用工备案的系统的网站,美食网站开发可行性分析报告,网页设计课程总结,wordpress怎么固定自定义栏目目录 前言模板朴素实现路径压缩按秩合并按树高为秩按节点数为秩 总结 前言 并查集的基本实现通常使用森林来表示不同的集合#xff0c;每个集合用一棵树表示#xff0c;树的每个节点有一个指向其父节点的指针。 如果一个节点是它自己的父节点#xff0c;那么它就是该集合的代… 目录 前言模板朴素实现路径压缩按秩合并按树高为秩按节点数为秩 总结 前言 并查集的基本实现通常使用森林来表示不同的集合每个集合用一棵树表示树的每个节点有一个指向其父节点的指针。 如果一个节点是它自己的父节点那么它就是该集合的代表称为根节点。 模板 P3367 【模板】并查集 https://www.luogu.com.cn/problem/P3367 题目描述
如题现在有一个并查集你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N , M N,M N,M ,表示共有 N N N 个元素和 M M M 个操作。
接下来 M M M 行每行包含三个整数 Z i , X i , Y i Z_i,X_i,Y_i Zi,Xi,Yi 。
当 Z i 1 Z_i1 Zi1 时将 X i X_i Xi 与 Y i Y_i Yi 所在的集合合并。
当 Z i 2 Z_i2 Zi2 时输出 X i X_i Xi 与 Y i Y_i Yi 是否在同一集合内是的输出 Y 否则输出 N 。
输出格式
对于每一个 Z i 2 Z_i2 Zi2 的操作都有一行输出每行包含一个大写字母为 Y 或者 N 。
**样例输入 **
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4样例输出
N
Y
N
Y提示
对于 15 % 15\% 15% 的数据 N ≤ 10 N \le 10 N≤10 M ≤ 20 M \le 20 M≤20。
对于 35 % 35\% 35% 的数据 N ≤ 100 N \le 100 N≤100 M ≤ 1 0 3 M \le 10^3 M≤103。
对于 50 % 50\% 50% 的数据 1 ≤ N ≤ 1 0 4 1\le N \le 10^4 1≤N≤104 1 ≤ M ≤ 2 × 1 0 5 1\le M \le 2\times 10^5 1≤M≤2×105。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 2 × 1 0 5 1\le N\le 2\times 10^5 1≤N≤2×105 1 ≤ M ≤ 1 0 6 1\le M\le 10^6 1≤M≤106 1 ≤ X i , Y i ≤ N 1 \le X_i, Y_i \le N 1≤Xi,Yi≤N Z i ∈ { 1 , 2 } Z_i \in \{ 1, 2 \} Zi∈{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)路径压缩不完全与按树高合并兼容因为路径压缩可以改变树的高度。 总结 并查集Union-Find 或 Disjoint Set Union, DSU是一种数据结构主要用于处理一些不相交集合的合并及查询问题。 如果有更多问题或需要进一步的帮助可以在评论区留言讨论哦 如果喜欢的话请给博主点个关注 谢谢
