深入理解并查集数据结构与实战应用

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

合并操作

合并时需比较两棵树的秩，将较小的树挂到较大的树下，避免树过高导致性能下降。

// 带按秩合并的合并操作
public void union(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] += 1;
        }
    }
}

优化技巧详解

路径压缩

在 find 过程中，将沿途所有节点的父节点直接设为根节点。这样下次再访问这些节点时，就能直接到达根部。虽然单次查找可能涉及递归，但摊还复杂度极低。

按秩合并

维护每棵树的高度估计值（秩）。合并时总是让高度低的树作为子树挂载到高度高的树上。这保证了树的高度增长缓慢，结合路径压缩后，整体效率极高。

完整代码示例

下面是一个封装好的并查集类，包含判断连通性的辅助方法。

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(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] += 1;
            }
        }
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    public void printParent() {
        for (int i = 0; i < parent.length; i++) {
            System.out.print(parent[i] + " ");
        }
        System.out.println();
    }
}

测试逻辑也很简单，实例化后执行几次合并与查询即可验证。

实战场景

图的连通性

这是并查集最经典的应用。比如在 Kruskal 算法求最小生成树时，利用并查集可以快速判断加入某条边是否会形成环。

社交网络分析

用户关系可以看作图，通过并查集能快速判断两个用户是否处于同一个社交圈子（即是否存在间接连接）。

动态连通性问题

适用于元素集合频繁合并、查询的场景，如网络故障排查、岛屿数量统计等。

时间复杂度

• 初始化：O(n)
• 查找（带路径压缩）：摊还复杂度 O(α(n))，其中 α(n) 是阿克曼函数的反函数，增长极慢，实际应用中可视为常数。
• 合并（带按秩合并）：同样接近 O(α(n))。

例题实战

题目一：水位上升的泳池中游泳

问题描述： 在一个 n x n 的整数矩阵 grid 中，grid[i][j] 表示位置 (i, j) 的平台高度。时间为 t 时，水位为 t。你可以从当前平台游向四周相邻平台，前提是水位同时淹没这两个平台。求从左上角 (0, 0) 到达右下角 (n-1, n-1) 所需的最少时间。

思路解析： 这道题本质上是动态连通性问题。随着时间推移，水位上升，原本不连通的格子会逐渐被淹没并连通。我们可以利用并查集维护格子的连通状态。

1. 映射坐标：将二维坐标转换为一维索引，方便并查集处理。
2. 排序处理：按高度从小到大处理每个格子，模拟水位上升过程。
3. 动态合并：对于当前高度的格子，检查其上下左右四个方向。如果相邻格子高度小于等于当前水位，说明它们已连通，执行 union 操作。
4. 判断终点：每次合并后检查起点和终点是否连通，一旦连通，当前时间即为答案。

代码实现：

private int N;
private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int swimInWater(int[][] grid) {
    this.N = grid.length;
    int len = N * N;
    // 建立高度到坐标的映射关系
    int[] index = new int[len];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            index[grid[i][j]] = getIndex(i, j);
        }
    }

    UnionFind uf = new UnionFind(len);
    // 按高度顺序处理
    for (int i = 0; i < len; i++) {
        int x = index[i] / N;
        int y = index[i] % N;
        // 检查四个方向
        for (int[] d : DIRECTIONS) {
            int newX = x + d[0];
            int newY = y + d[1];
            if (inArea(newX, newY) && grid[newX][newY] <= i) {
                uf.union(index[i], getIndex(newX, newY));
            }
        }
        // 检查起点终点是否连通
        if (uf.isConnected(0, len - 1)) {
            return i;
        }
    }
    return -1;
}

private int getIndex(int x, int y) {
    return x * N + y;
}

private boolean inArea(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 内部并查集类
private class UnionFind {
    private int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int root(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]]; // 路径压缩
            x = parent[x];
        }
        return x;
    }

    public boolean isConnected(int x, int y) {
        return root(x) == root(y);
    }

    public void union(int p, int q) {
        if (isConnected(p, q)) return;
        parent[root(p)] = root(q);
    }
}

题目二：省份数量

问题描述： 给定 n x n 的邻接矩阵 isConnected，isConnected[i][j] = 1 表示城市 i 和 j 直接相连。省份是一组直接或间接相连的城市。求省份的数量。

解题思路： 这是一个典型的连通分量计数问题。初始时每个城市自成一个集合，遍历矩阵，若发现两个城市相连，则合并它们的集合。最终集合的数量即为省份数。

代码实现：

public int findCircleNum(int[][] isConnected) {
    if (isConnected == null || isConnected.length == 0) return 0;
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (isConnected[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }
    return uf.getCount();
}

class UnionFind {
    int[] root;
    int[] rank;
    int count;

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        count = size;
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (x == root[x]) return x;
        return root[x] = find(root[x]);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}

总结

并查集通过简单的数组结构和巧妙的优化策略，实现了高效的集合操作。掌握路径压缩和按秩合并是理解其性能的关键。在实际开发中，遇到涉及分组、连通性判断的问题，不妨优先考虑并查集方案。