并查集数据结构详解与实战应用

3.3 合并与按秩合并

合并两个集合时，为了避免树退化成链表，我们采用按秩合并策略：始终将较矮的树挂到较高的树上。

// 带按秩合并的合并操作
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;
        }
    }
}

3.4 完整工具类

为了方便使用，我们可以封装一些辅助方法，如判断连通性和打印调试信息。

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 static void main(String[] args) {
        int n = 10;
        UnionFind uf = new UnionFind(n);
        uf.union(1, 2);
        uf.union(2, 5);
        uf.union(6, 7);
        
        System.out.println("Is 1 and 5 connected? " + uf.isConnected(1, 5)); // true
        System.out.println("Is 6 and 7 connected? " + uf.isConnected(6, 7)); // true
        System.out.println("Is 1 and 3 connected? " + uf.isConnected(1, 3)); // false
    }
}

4. 时间复杂度分析

• 初始化：O(n)
• 查找与合并：经过路径压缩和按秩合并优化后，单次操作的摊还时间复杂度接近常数级 O(α(n))，其中 α(n) 是阿克曼函数的反函数，增长极慢。

二、例题实战

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

题目链接：力扣 778

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

解题思路： 这是一个典型的动态连通性问题。随着时间推移，水位上升，原本不连通的格子可能变得连通。我们可以利用并查集来维护格子的连通状态。

1. 排序：将所有格子按高度从小到大排序。
2. 遍历合并：按高度顺序处理每个格子，将其与周围高度更低或相等的已处理格子合并。
3. 检查连通：每次合并后，检查起点和终点是否连通。一旦连通，当前高度即为答案。

代码实现：

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 unionFind = new UnionFind(len);
    
    // 按高度顺序处理
    for (int i = 0; i < len; i++) {
        int x = index[i] / N;
        int y = index[i] % N;
        
        for (int[] direction : DIRECTIONS) {
            int newX = x + direction[0];
            int newY = y + direction[1];
            
            if (inArea(newX, newY) && grid[newX][newY] <= i) {
                unionFind.union(index[i], getIndex(newX, newY));
            }
        }
        
        if (unionFind.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);
    }
}

例题二：省份数量

题目链接：力扣 547

问题描述： 给定一个 n x n 的矩阵 isConnected，isConnected[i][j] = 1 表示城市 i 和城市 j 直接相连。返回省份的数量（即连通分量的数量）。

解题思路： 将每个城市视为一个节点，直接相连的城市合并到同一个集合。最终统计集合的数量即可。

1. 初始化：创建包含 n 个城市的并查集。
2. 遍历矩阵：对于每对直接相连的城市，执行 union 操作。
3. 统计结果：记录成功合并的次数或直接统计根节点数量。

代码实现：

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;
    }
}

总结

并查集在处理动态连通性问题时表现优异，其核心优势在于高效的查找与合并能力。通过路径压缩和按秩合并，我们可以将操作复杂度降至近乎常数。在实际开发中，无论是图的连通性判断、最小生成树构建，还是社交网络关系分析，并查集都是值得掌握的基础工具。希望上述原理讲解与代码实战能帮助你更好地理解和应用这一数据结构。