跳到主要内容

并查集

什么是并查集？​

并查集（Disjoint Set Union，简称 DSU）是一种用于管理元素分组和查找的高效数据结构。它支持两种主要操作：

  1. 查找（Find）：确定某个元素属于哪个集合。
  2. 合并（Union）：将两个集合合并为一个集合。

并查集的核心思想是通过树结构来表示集合，并通过路径压缩和按秩合并等优化技术来提高效率。

并查集的基本操作​

1. 初始化​

每个元素最初都是一个独立的集合，其父节点指向自己。

python
parent = [i for i in range(n)]  # n 是元素的总数

2. 查找（Find）​

查找操作用于确定某个元素的根节点（即集合的代表）。通过递归查找父节点，直到找到根节点。

python
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 路径压缩优化
    return parent[x]

3. 合并（Union）​

合并操作将两个集合合并为一个集合。通常通过将其中一个集合的根节点指向另一个集合的根节点来实现。

python
def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_x] = root_y  # 将 x 的根节点指向 y 的根节点

优化技术​

1. 路径压缩​

在查找操作中，将路径上的所有节点直接连接到根节点，以减少后续查找的时间复杂度。

2. 按秩合并​

在合并操作中，将较小的树连接到较大的树上，以保持树的平衡性。

python
rank = [1] * n  # 初始化每个集合的秩

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        if rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        elif rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

实际案例​

案例 1：连通性问题​

假设有一组城市和连接它们的道路。我们需要判断两个城市是否连通。

python
# 初始化
n = 5  # 5 个城市
parent = [i for i in range(n)]
rank = [1] * n

# 连接城市
union(0, 1)
union(2, 3)
union(1, 4)

# 检查连通性
print(find(0) == find(4))  # 输出: True
print(find(2) == find(4))  # 输出: False

案例 2：图论中的环检测​

在无向图中，检测是否存在环。

python
# 初始化
n = 4  # 4 个节点
parent = [i for i in range(n)]
rank = [1] * n

# 边列表
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]

# 检测环
has_cycle = False
for u, v in edges:
    if find(u) == find(v):
        has_cycle = True
        break
    union(u, v)

print(has_cycle)  # 输出: True

总结​

并查集是一种高效的数据结构，适用于解决连通性问题、图论中的环检测以及动态连通性场景。通过路径压缩和按秩合并等优化技术，可以显著提高其性能。

附加资源与练习​

练习​

  1. 实现一个并查集，并测试其查找和合并操作。
  2. 使用并查集解决一个实际问题，例如社交网络中的朋友关系。

资源​