1.题目
给定一个序列，通过n-1次相邻元素的合并操作，恢复原始序列。
2.涉及知识点 - 并查集 (Union-Find)
并查集 (Union-Find) 详解
概述
并查集（Union-Find），也称为不相交集数据结构，用于处理一些不相交集合（Disjoint Sets）的合并（Union）及查询（Find）问题。并查集是一种高效的数据结构，常用于图论中的连通性问题，如判断两个元素是否属于同一个集合。
基本概念
- 代表元（代表元素）：每个集合有一个特别的元素作为其代表元，集合的所有操作通过代表元来完成。（某个集合的一个代表。用于表示这个集合 ）
- 合并操作（Union）：将两个不同的集合合并为一个集合。
- 查找操作（Find）：确定某个元素属于哪个集合，返回集合的代表元。
基本实现
并查集可以用两种方法来实现：数组实现和树实现。通常，树实现更常用，因为它更高效（其实本身就是树形结构，数组实现和树实现只是一个称呼而已。）
数组实现
在数组实现中，并查集用一个简单的数组来表示，每个元素的值指向它所属集合的代表元素。（他爹，不是整个家族的爹）
特点
- 简单：实现起来非常简单，直观地通过数组的索引来操作。
- 效率低：在合并操作中，需要遍历整个数组来更新代表元素，时间复杂度为 (O(n))。
代码示例
class UnionFindArray:
def __init__(self, n):
self.parent = list(range(n)) # 初始化，每个元素的父节点指向自己
def find(self, x):
return self.parent[x] # 查找操作，返回代表元
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
for i in range(len(self.parent)):
if self.parent[i] == rootY:
self.parent[i] = rootX # 合并操作
这里实际上就find操作，只是找到当前元素的父亲，而不是整个集合的父亲。然后再进行合并操作的时候。他会把每一个元素他的父亲都给刷新一遍。所以效率是比较低的。
劣势
- 合并操作效率低：每次合并需要遍历整个数组，导致时间复杂度较高。
- 没有路径压缩：没有优化查找操作，会导致查找操作效率低下。
更好的方法是通过更新根节点来实现合并，而不是遍历整个数组。可以使用路径压缩和按秩合并来优化这个过程。（最大的区别）
下面是使用路径压缩和按秩合并的并查集实现，它在合并操作时只更新根节点的父节点，并保持树的平衡：
优化的并查集实现 - 树实现
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # 初始化，每个元素的父节点指向自己，索引表示父节点
self.rank = [1] * n # 初始化，每棵树的秩为1，每个位置都是一个节点，这里长度为n，每个都是1
def find(self, x):
if self.parent[x] != x: # 父节点不是自己的
self.parent[x] = self.find(self.parent[x]) # 路径压缩（递归设置他爸）
return self.parent[x] # 通过孩返回他爹
def union(self, x, y):
# 选取的两个元素他爹
rootX = self.find(x)
rootY = self.find(y)
# 两爹不一样，表示不在一个集合里面，不是一家人
if rootX != rootY:
# 按秩合并
# rootx家里辈分高（注意秩指的是树的高度），就把rooty以及家里人认rootx做爹
# 父亲与父亲之间的较量，谁辈分小就得认另外一个做爹
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
# 随意
self.parent[rootY] = rootX
self.rank[rootX] += 1 # 只有秩相同时才增加秩
树结构最大的区别就是，它用了这个递归去把每一个元素提前把父亲给找好了。这样的话，我们去找集合里面的根节点是就比较方便。
随便找这个集合里面的某一个元素就可以找到当前集合的根节点，而不是当前元素的父节点
秩操作解释
秩（Rank）在并查集中表示树的高度或者近似高度。按秩合并的基本思想是将高度较低的树连接到高度较高的树上，以保持树的整体高度尽量低，从而加快后续的查找操作。
秩的定义
在并查集中，秩可以定义为树的高度或者树中节点的最大深度。初始时，每个节点自己独立构成一个集合，其秩为 1。随着集合的合并，树的高度可能增加，我们通过秩来记录这种变化。
为什么秩相同时才增加秩
当我们合并两个集合时，有以下几种情况：
-
树的秩不同
- 如果一棵树的秩大于另一棵树，我们将秩较小的树的根节点连接到秩较大的树的根节点上。
- 这种情况下，合并后的树的高度不会增加，因为较小的树的节点都连接到较大的树中，不会影响较大的树的高度。
-
树的秩相同
- 如果两棵树的秩相同，我们将其中一棵树的根节点连接到另一棵树的根节点上。
- 这种情况下，合并后的树的高度会增加 1，因为两棵树的高度相同，连接后新的根节点的深度增加了1
-
路径压缩：
在find操作中，我们递归地找到根节点，并将路径上所有节点的父节点直接设为根节点。这减少了树的高度，加速了后续的操作。 -
按秩合并：
在union操作中，我们比较两个树的秩，将秩较小的树连接到秩较大的树上。如果两棵树的秩相同，我们将其中一棵树连接到另一棵树上，并增加根节点的秩。这保持了树的平衡，避免退化为链表。
优化的合并操作的优势
- 效率高：不需要遍历整个数组，只需要更新根节点的父节点。
- 路径压缩：减少树的高度，加速后续的
find操作。 - 按秩合并：保持树的平衡，避免退化为链表。
示例使用
# 初始化并查集
uf = UnionFind(5)
# 合并操作
uf.union(0, 1)
uf.union(1, 2)
# 查找操作
print(uf.find(0)) # 输出: 0
print(uf.find(1)) # 输出: 0
print(uf.find(2)) # 输出: 0
print(uf.find(3)) # 输出: 3
# 合并操作
uf.union(3, 4)
# 查找操作
print(uf.find(3)) # 输出: 3
print(uf.find(4)) # 输出: 3
# 合并两个集合
uf.union(0, 3)
# 查找操作
print(uf.find(0)) # 输出: 0
print(uf.find(4)) # 输出: 0
适用于各种动态连通性问题。
并查集的应用
- 网络连通性：判断网络中的节点是否连通。
- 最小生成树：Kruskal算法需要使用并查集来检测是否形成环。
- 动态连通性问题：动态维护元素之间的连通关系。
性能分析
由于路径压缩和按秩合并的使用，并查集的时间复杂度接近常数级别。具体来说，查找和合并操作的平均时间复杂度是 O(n)， 增长极其缓慢，在实际应用中可以视为常数。
例题
例题1: 判断连通性
给定一组节点和边，判断任意两点是否连通。
def are_connected(edges, n, query):
# 这里假设这个函数已经写好了。就相当于是上面我们写的寻找代表元函数。
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
# 两个代表元相等说明联通返回真
return uf.find(query[0]) == uf.find(query[1])
# 示例
edges = [(0, 1), (1, 2), (3, 4)]
n = 5
query = (0, 2)
print(are_connected(edges, n, query)) # 输出: True
例题2: 朋友圈问题
有一个包含 (n) 个人的社交网络，每个人都是一个朋友圈。给定一些朋友关系，请计算有多少个独立的朋友圈。
def find_circle_num(M):
n = len(M)
uf = UnionFind(n)
# 同样就是不断地去找，然后计数就行。
for i in range(n):
for j in range(i+1, n):
if M[i][j] == 1:
uf.union(i, j)
return len(set(uf.find(i) for i in range(n)))
# 示例
M = [
[1, 1, 0],
[1, 1, 0],
[0, 0, 1]
]
print(find_circle_num(M)) # 输出: 2
下面的这道题，就是用并查集来解决。
3.解决方案
给定一个序列，通过n-1次相邻元素的合并操作，恢复原始序列
关于这道题，我们先看一位up主的解决方案。(@bilbil轩哥码题)
#include <iostream>
using namespace std;
const int N = 1e7;
int n ,fa[N],so[N],nxt[N];
void init(int n){
for(int i=1;i<=n;i++){
fa[i] = i;
so[i] = i;
}
}
// 这里实际上就是数组法，每次都要去遍历寻找
int find(int x ){
// x本身不是自己的父节点，说明x不是一个根结点
// 则递归调用当前函数，一直找到当前节点的根结点，后面那段代码表示去找当前节点的父节点的父节点，直到找到根结点
return x ==fa[x] ? x:(fa[x] = find(fa[x]));
}
void merge(int i, int j){
int x = find(i);
int y = find(j);
// 表示两个不在一个集合里面
if(x!=y)
{
// 这里是做合并操作
nxt[so[x]] = y;
fa[y] =x;
so[x] = so[y];
}
}
int main(){
cin>>n;
// 初始每个元素的父节点为自己
init(n);
// 循环合并每个集合
for(int i =1;i<n;i++){
int x,y;
cin>>x>>y;
merge(x,y);
}
// 这里是每个集合都合并了，然后按照根结点开始遍历这棵树
// 所以find(1)这里的数字是什么都可以的，然后每次循环更新游标为根结点的儿子就好
for (int i=find(1);i;i = nxt[i]){
cout<<i<<" ";
}
return 0;
}
这里很显然可以看到他的思路就是我们上面说的数组法，每次寻找父节点都需要去遍历一遍。 那么下面呢，我们按照树去优化一下。
# 初始化
def init(n):
global fa, so, nxt
fa = list(range(n + 1)) # 父节点初始化为自己
so = list(range(n + 1)) # 儿子节点初始化为自己
nxt = [0] * (n + 1) # next节点初始化为0
# 查找根节点并进行路径压缩
def find(x):
if x == fa[x]:
return x
fa[x] = find(fa[x])
return fa[x]
# 合并两个节点
def merge(i, j):
x = find(i)
y = find(j)
if x != y:
nxt[so[x]] = y
fa[y] = x
so[x] = so[y]
# 主函数
def slime_fusion(n, fusion_steps):
init(n)
for x, y in fusion_steps:
merge(x, y)
result = []
i = find(1)
while i:
result.append(i)
i = nxt[i]
return result
# 输入处理
n = int(input().strip())
fusion_steps = [tuple(map(int, input().strip().split())) for _ in range(n-1)]
# 计算并输出结果
result = slime_fusion(n, fusion_steps)
print(" ".join(map(str, result)))
并查集浅谈，希望对你有所帮助
