并查集（Union-Find）是一种树形的数据结构，用于处理不相交集合（也称为离散集合）的合并和查询问题。它主要用于动态连通性问题，即确定元素是否属于同一个集合。并查集的两个主要操作是“合并”（Union）和“查找”（Find），所以得名“并查集”。

1. 基本概念

  • 集合（Set）：一组不相交的元素，也就是说，每个集合中的元素都是唯一的，集合之间没有交集。
  • 合并（Union）：将两个不同的集合合并成一个集合。
  • 查找（Find）：找到一个元素所在集合的代表元素（根节点），通常用于判断两个元素是否在同一个集合中。

2. 树形表示

在并查集中，每个集合可以用一棵树来表示，树的根节点代表整个集合。集合中的每个元素都是树中的一个节点，且每个节点都有一个指向其父节点的指针。

  • 根节点（Root）：一个集合的代表元素，它是树的根。查找操作的结果就是某个元素的根节点。
  • 路径压缩（Path Compression）：在查找操作中，通过将树上的所有节点直接连接到根节点来扁平化树结构，从而加速后续的查找操作。

3. 并查集的操作

查找（Find）

找到元素所在集合的根节点。

1
2
3
4
5
6
int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

合并（Union）

将两个集合合并为一个集合，通常使用按秩合并（Union by Rank）或按大小合并（Union by Size）来优化合并操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            fa[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            fa[rootX] = rootY;
        } else {
            fa[rootY] = rootX;
            rank[rootX] += 1;
        }
    }
}

4. 并查集的优化

  1. 路径压缩（Path Compression）：在查找时将树“扁平化”，使得树的高度变小，从而加速后续查找操作。
  2. 按秩合并（Union by Rank）：总是将秩（即树的高度）较小的树合并到秩较大的树上，以保持树的高度尽量小。
  3. 按大小合并（Union by Size）：总是将节点数量较少的树合并到节点数量较多的树上。

5. 使用场景

并查集常用于以下场景：

  • 网络连通性：判断网络中的两个节点是否连通。
  • 动态连通性问题：如图的连通分量计算。
  • 最小生成树：Kruskal算法中使用并查集来检测环路。

6. 总结

并查集是一种高效解决动态连通性问题的数据结构。通过路径压缩和按秩合并的优化，可以实现几乎常数时间的合并和查找操作。掌握并查集对于解决很多图论问题和网络连通性问题非常有帮助。

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解答

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
class Solution {
public:
    // 并查集的初始化
    unordered_map<int, int> fa; // 储存每个节点的root，初始化为自己
    unordered_map<int, int> size; // 储存以当前节点为root的节点数量，初始化只有自己一个节点

    // 查找操作
    int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    // 合并操作
    void merge(int f, int to) {
        f = find(f);
        to = find(to);
        if (f != to) {
            fa[f] = to;
            size[to] += size[f];
        }
    }

    int longestConsecutive(vector<int>& nums) {
        // 去重
        unordered_set<int> numSet(nums.begin(), nums.end());
        int ans = 0;

        for (int num : numSet) {
            fa[num] = num;
            size[num] = 1;
        }

        // 遍历集合并合并
        for (int num : numSet) {
            if (numSet.count(num + 1)) {
                merge(num, num + 1);
            }
        }

        // 计算最长连续序列的长度
        for (auto& [key, value] : size) {
            ans = max(ans, value);
        }

        return ans;
    }
};