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

认识并查集

并查集（Disjoint Set）是一种用于管理不相交集合的数据结构，核心在于高效处理动态的集合合并与查询操作。它主要支持两个基本功能：

• Find（查找）：确定某个元素属于哪一个集合。
• Union（合并）：将两个元素所在的集合合并为一个集合。

核心原理

集合表示

并查集通常通过一个数组（parent 数组）来表示每个元素的父节点，从而形成森林结构。每个集合用一棵树表示，树的根节点即为该集合的代表元素。初始状态下，每个元素都是一个独立的集合，父节点指向自己。

例如，有 5 个元素（0 到 4），初始 parent 数组为 [0, 1, 2, 3, 4]。

优化技巧

为了提升效率，实际应用中通常会结合两种优化策略：

1. 路径压缩：在查找操作中，将查找路径上的所有节点直接指向根节点，减少后续查找的深度。
2. 按秩合并：在合并操作中，总是将秩（树的高度或深度）较小的树合并到秩较大的树上，避免树变得过高。

完整代码示例

下面是一个包含路径压缩和按秩合并优化的 Java 实现。初始化时每个元素父节点指向自身，查找时递归更新父节点，合并时比较秩的大小决定连接方向。

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

应用场景

并查集在处理连通性问题时非常高效，常见场景包括：

• 图的连通性：判断图中是否存在环，或两个节点是否连通。例如 Kruskal 算法构建最小生成树时，利用并查集判断边是否会形成环。
• 社交网络分析：判断两个用户是否属于同一个社交圈子。
• 动态连通性问题：适用于需要频繁更新连通性状态的场景，如网络故障检测等。

实战演练

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

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

思路解析： 这道题本质上是动态连通性问题。随着时间推移，水位上升，原本不连通的平台可能变得连通。我们可以按高度从小到大排序所有格子，依次激活并合并相邻且高度小于等于当前水位的格子。一旦起点和终点连通，当前时间即为答案。

代码实现：

private int N;
public 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;
}

例题二：省份数量

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

思路解析： 将每个城市视为一个元素，遍历邻接矩阵。如果城市 i 和城市 j 直接相连，则执行 union 操作。最终统计连通分量的数量即可。可以通过维护一个 count 变量，每次成功合并时减 1。

代码实现：

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;

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

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

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

    int getCount() {
        return count;
    }
}

复杂度分析

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

这种高效的特性使得并查集在处理大规模数据时依然表现优异。