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

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

并查集广泛应用于解决动态连通性问题，例如判断图中的两个节点是否连通、统计连通分量等。

1. 核心思想

并查集的核心思想是用一个父节点数组来表示每个元素的所属集合。初始时，每个元素都是一个独立的集合，父节点指向自己。通过路径压缩和按秩合并等优化技术，可以高效地支持查找和合并操作。

2. 基本操作

（1）初始化

  • 每个元素初始时都是一个独立的集合，父节点指向自己。
  • 例如，有 5 个元素：[0, 1, 2, 3, 4]，初始化后父节点数组为 parent = [0, 1, 2, 3, 4]。

（2）查找（Find）

  • 查找某个元素所属的集合（即根节点）。
  • 通过递归或迭代的方式，沿着父节点向上查找，直到找到根节点。
  • 路径压缩优化：在查找过程中，将路径上的所有节点直接指向根节点，以加快后续查找速度。

（3）合并（Union）

  • 将两个元素所在的集合合并为一个集合。
  • 先找到两个元素的根节点，然后将其中一个根节点的父节点指向另一个根节点。
  • 按秩合并优化：在合并时，将较小的树合并到较大的树上，以保持树的平衡。

3. 并查集的实现

以下是并查集的 Python 实现，包含路径压缩和按秩合并优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class UnionFind:
    def __init__(self, n):
        # 初始化父节点数组和秩数组
        self.parent = list(range(n))  # 每个元素的父节点初始为自己
        self.rank = [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):
        # 合并两个集合
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x != root_y:
            # 按秩合并
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

4. 并查集的应用场景

  1. 动态连通性问题：

    • 判断两个节点是否连通。
    • 统计图中的连通分量。

  2. 最小生成树算法（Kruskal 算法）：

    • 用于判断边的两个端点是否属于同一集合。

  3. 朋友圈问题：

    • 给定一组朋友关系，判断有多少个朋友圈。

  4. 图像处理：

    • 用于像素连通区域的标记。

5. 并查集的时间复杂度

  • 初始化：O(n)，其中 n 是元素个数。
  • 查找（Find）：接近 O(1)，经过路径压缩后，查找操作的时间复杂度接近常数。
  • 合并（Union）：接近 O(1)，经过按秩合并优化后，合并操作的时间复杂度接近常数。

6. 并查集的优化

  1. 路径压缩：

    • 在查找过程中，将路径上的所有节点直接指向根节点，以加快后续查找速度。

  2. 按秩合并：

    • 在合并时，将较小的树合并到较大的树上，以保持树的平衡，避免树过高。

7. 并查集的经典问题

（1）判断图中是否有环

  • 遍历图中的每条边，如果两个端点属于同一集合，则说明存在环。

（2）统计连通分量

  • 遍历所有节点，统计不同根节点的个数。

（3）朋友圈问题

  • 给定一组朋友关系，判断有多少个朋友圈（连通分量）。

8. 代码示例：朋友圈问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    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):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

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

总结

并查集是一种高效管理分组的数据结构，核心操作是查找和合并。通过路径压缩和按秩合并优化，可以显著提高性能。它在动态连通性问题、最小生成树算法、朋友圈问题等场景中有广泛应用。

以下是使用 C++ 实现的并查集代码，包含路径压缩和按秩合并优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent; // 父节点数组
    vector<int> rank;   // 秩数组

public:
    // 构造函数，初始化并查集
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 1); // 初始时每个集合的秩为 1
        for (int i = 0; i < n; i++) {
            parent[i] = i; // 每个元素的父节点初始为自己
        }
    }

    // 查找操作，带路径压缩
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并操作，带按秩合并
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            // 按秩合并
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    // 判断两个元素是否属于同一集合
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 5; // 元素个数
    UnionFind uf(n);

    // 合并操作
    uf.unionSets(0, 1);
    uf.unionSets(2, 3);
    uf.unionSets(1, 4);

    // 判断是否连通
    cout << "0 and 4 are connected: " << uf.isConnected(0, 4) << endl; // 输出: 1 (true)
    cout << "2 and 4 are connected: " << uf.isConnected(2, 4) << endl; // 输出: 0 (false)

    return 0;
}

代码说明

  1. 初始化：

    • parent 数组存储每个元素的父节点，初始时每个元素的父节点是自己。
    • rank 数组存储每个集合的秩（树的高度），初始时为 1。

  2. 查找操作（find）：

    • 通过递归查找根节点，并在查找过程中进行路径压缩，将路径上的所有节点直接指向根节点。

  3. 合并操作（unionSets）：

    • 找到两个元素的根节点，按秩合并（将较小的树合并到较大的树上）。

  4. 判断连通性（isConnected）：

    • 判断两个元素的根节点是否相同。

示例运行

输入：

1
2
3
4
5
int n = 5;
UnionFind uf(n);
uf.unionSets(0, 1);
uf.unionSets(2, 3);
uf.unionSets(1, 4);

输出：

1
2
0 and 4 are connected: 1
2 and 4 are connected: 0

并查集的应用

  1. 动态连通性问题：

    • 判断两个节点是否连通。
    • 统计连通分量。

  2. 最小生成树算法（Kruskal 算法）：

    • 用于判断边的两个端点是否属于同一集合。

  3. 朋友圈问题：

    • 给定一组朋友关系，判断有多少个朋友圈。

总结

并查集是一种高效管理分组的数据结构，核心操作是查找和合并。通过路径压缩和按秩合并优化，可以显著提高性能。以上代码是 C++ 实现的标准模板，适用于大多数并查集相关的问题。