实战：并查集（Union-Find + 路径压缩）

并查集这东西，我第一次接触是在大学的数据结构课上。当时觉得不就是几个集合嘛，有啥好学的？直到后来做社交网络的好友关系分析，才发现这玩意儿简直是处理「连通性」问题的瑞士军刀。今天咱们就把它彻底搞明白。

什么是并查集？

说白了，并查集就是用来管理「元素分组」的数据结构。它支持两个操作：

• 查找（Find）：判断某个元素属于哪个组
• 合并（Union）：把两个组合并成一个

你想想看，如果让你判断两个人是不是朋友的朋友的朋友... 用并查集，几行代码就搞定了。

核心思想：树形结构

并查集的底层实现其实是一棵树。每个节点指向它的父节点，根节点代表这个集合的「老大」。判断两个元素是否在同一个集合，就看它们的根节点是不是同一个。

基础实现

先看最朴素的版本。我习惯用一个数组 parent[] 来存储每个节点的父节点：

class UnionFind {
private:
    vector<int> parent;
    
public:
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 初始时，每个节点都是自己的老大
        }
    }
    
    int find(int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }
    
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;  // 把y的根挂到x的根下面
        }
    }
    
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

嗯，这里要注意。上面的 find 函数是递归往上找，如果树很深，效率会很低。我在项目中遇到过一棵树深度达到几万的情况，直接导致栈溢出。所以必须优化。

路径压缩：让树变矮

路径压缩的思路很简单：在 find 的过程中，把沿途经过的节点直接指向根节点。这样下次再查的时候，一步就到位了。

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 递归压缩路径
    }
    return parent[x];
}

你看，就加了一行代码。但效果立竿见影。经过路径压缩后，树的高度几乎不会超过 4。这就是所谓的「几乎常数时间」操作。

按秩合并：另一种优化

路径压缩是「查」的优化，按秩合并是「并」的优化。思路是：把矮的树挂到高的树下面，避免树长歪。

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;  // 记录树的高度（秩）
    
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        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) return;
        
        // 按秩合并：矮树挂到高树下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
};

路径压缩 + 按秩合并，这两个优化一起用，时间复杂度可以降到反阿克曼函数级别。说白了，就是近乎常数时间。我在做图算法优化时，这个组合从来没让我失望过。

实战案例：朋友圈问题

我记得有一次面试，面试官问了一个经典问题：

「有 n 个人，给定他们之间的朋友关系，判断这些人能分成几个朋友圈？」

用并查集，三分钟搞定：

int findCircleNum(vector<vector<int>>& M) {
    int n = M.size();
    UnionFind uf(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (M[i][j] == 1) {
                uf.unionSets(i, j);
            }
        }
    }
    
    // 统计有多少个不同的根
    unordered_set<int> roots;
    for (int i = 0; i < n; i++) {
        roots.insert(uf.find(i));
    }
    return roots.size();
}

你看，核心逻辑就几行。剩下的都是模板代码。

并查集的核心逻辑

下面这张图展示了并查集从初始化到路径压缩的完整流程：

避坑指南

性能对比

我整理了一份不同实现方式的性能对比，方便你选型：

实现方式	find 时间复杂度	union 时间复杂度	适用场景
朴素实现	O(n)	O(n)	数据量小（n < 1000）
路径压缩	O(α(n))	O(α(n))	查询频繁
按秩合并	O(log n)	O(log n)	合并频繁
路径压缩 + 按秩合并	O(α(n))	O(α(n))	通用场景（推荐）

α(n) 是反阿克曼函数，增长极慢。n 取宇宙中原子数时，α(n) 也不超过 5。所以你可以认为它就是常数时间。

总结

并查集的核心就三点：

1. 用树表示集合，根节点是代表元素
2. 路径压缩让树变矮，find 几乎常数时间
3. 按秩合并防止树长歪，union 也几乎常数时间

我个人建议，不管题目大小，都直接把路径压缩和按秩合并写上。反正就几行代码，写上去不吃亏。等你遇到大数据量的时候，就知道这有多香了。

---

公众号:蓝海资料掘金营，微信deep3321