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

一、认识并查集

1. 并查集的定义

并查集是一种用于管理不相交集合（Disjoint Set）的数据结构。它主要用于处理一些需要动态维护集合的合并和查询操作的问题。并查集的核心功能是高效地支持以下两个基本操作：

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

2. 基本概念

2.1. 集合的表示

并查集通过一个数组（通常称为 parent 数组）来表示每个元素的'父节点'，从而形成一个森林结构。每个集合用一个树来表示，树的根节点即为该集合的代表元素。 例如，假设我们有 5 个元素（0, 1, 2, 3, 4），初始时每个元素都是一个独立的集合： 0 1 2 3 4 对应的 parent 数组为：[0, 1, 2, 3, 4] 每个元素的父节点指向自己，表示每个元素都是一个独立的集合。

2.2. 合并操作

当我们需要将两个元素所在的集合合并时，可以通过将一个集合的根节点指向另一个集合的根节点来实现。例如，将元素 1 和元素 0 所在的集合合并：

0 1 2 3 4 \ / 1

此时对应的 parent 数组变为：[1, 1, 2, 3, 4] 此时，元素 1 和元素 0 属于同一个集合，集合的根节点是 1。

2.3. 查询操作

查询某个元素属于哪个集合时，我们只需要找到该元素所在树的根节点。例如，查询元素 2 属于哪个集合：find(0) -> find(1) -> 1

元素 0 的根节点是 1，因此元素 2 属于根节点为 1 的集合。

3. 基本操作

3.1 初始化

初始化时，每个元素的父节点指向自己，表示每个元素初始时都是一个独立的集合。

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;        // 每个元素的秩初始化为 0
        }
    }
}

3.2. 查找

查找操作的目的是找到某个元素所在的集合的根节点。为了提高效率，通常会使用路径压缩技术，即将查找路径上的所有节点直接指向根节点。

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

3.3. 合并

合并操作是将两个元素所在的集合合并为一个集合。通常会使用**按秩合并（Union by Rank）或按大小合并（Union by Size）**来优化合并操作，避免树变得过高。

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

4. 优化技巧

4.1. 路径压缩

路径压缩是在查找操作中，将查找路径上的所有节点直接指向根节点，从而减少后续查找的深度。路径压缩的实现非常简单，只需要在 find 函数中添加一行代码即可。

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

4.2. 按秩合并

按秩合并是在合并操作中，总是将秩（树的高度或深度）较小的树合并到秩较大的树上，从而避免树变得过高。秩可以用一个额外的数组 rank 来记录。

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

5. 代码完整实例

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;        // 每个元素的秩初始化为 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();
    }

    // 打印当前的秩数组（用于调试）
    public void printRank() {
        for (int i = 0; i < rank.length; i++) {
            System.out.print(rank[i] + " ");
        }
        System.out.println();
    }
}

// 测试并查集
public class Main {
    public static void main(String[] args) {
        int n = 10; // 假设有 10 个元素
        UnionFind uf = new UnionFind(n);

        // 合并一些元素
        uf.union(1, 2);
        uf.union(2, 5);
        uf.union(6, 7);
        uf.union(3, 8);
        uf.union(8, 9);

        // 查询一些元素是否连通
        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

        // 打印当前的父节点数组和秩数组
        System.out.print("Parent array: ");
        uf.printParent();
        System.out.print("Rank array: ");
        uf.printRank();
    }
}

6. 应用场景

6.1. 图的连通性

并查集可以用于判断图中是否存在环，或者判断图中两个节点是否连通。例如，在最小生成树（Kruskal 算法）中，使用并查集来判断边是否会形成环。

6.2. 社交网络分析

在社交网络中，可以使用并查集来判断两个用户是否属于同一个社交圈子。

6.3. 动态连通性问题

并查集可以动态地处理元素的合并和查询操作，适用于需要频繁更新连通性状态的场景。

7. 时间复杂度

• 初始化：O(n)
• 查找（带路径压缩）：几乎为常数时间，摊还复杂度为 O(α(n))，其中 α(n) 是阿克曼函数的反函数，增长非常缓慢。
• 合并（带按秩合并）：几乎为常数时间，摊还复杂度为 O(α(n))。

二、例题实战

例题一

力扣 778、水位上升的泳池中游泳

1. 题目描述：

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。 当开始下雨时，在时间为 t 时，水池中的水位为 t。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。 你从坐标方格的左上平台 (0, 0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间。

示例 1：

示例 2：

2. 算法思路：

这道题目可以用并查集来解决，原因在于并查集能够高效地处理动态连通性问题，即在动态变化的环境中判断两个点是否连通。在这个问题中，随着时间的推移（水位的上升），原本不连通的平台可能会因为水位的升高而变得连通。并查集可以动态地维护这些平台之间的连通性，从而帮助我们找到从起点到终点的最短时间。

**动态连通性：**随着时间的推移，水位上升，原本不连通的平台可能会变得连通。并查集可以动态地处理这种连通性的变化。每当水位上升到某个高度时，所有高度小于或等于该水位的平台都会被淹没，这些平台之间可能会形成新的连通关系。

**高效性：**并查集的查找和合并操作在路径压缩和按秩合并的优化下，几乎可以认为是常数时间复杂度（摊还复杂度为 O(α(n))）。这使得它在处理大规模数据时非常高效。

3. 解题思路：

1. 初始化并查集： 初始化一个并查集，将矩阵中的每个平台视为一个独立的集合。
2. 排序平台高度： 将矩阵中的所有平台高度提取出来，并按高度从小到大排序。这样我们可以按顺序处理每个平台，确保水位逐渐上升。
3. 动态合并平台： 按高度从小到大的顺序处理每个平台。对于每个平台，检查其四个方向（上、下、左、右）的相邻平台。如果相邻平台已经被淹没（即高度小于或等于当前水位），则将当前平台与相邻平台合并到同一个集合中。
4. 判断连通性： 每次合并后，检查起点（0, 0）和终点（n-1, n-1）是否连通。如果连通，则当前水位即为所需最少时间。

4. 代码示例：

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); // 将高度为 grid[i][j] 的格子映射到坐标 (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));
            }

            // 检查起点 (0,0) 和终点 (N-1,N-1) 是否连通
            if (unionFind.isConnected(0, len - 1)) {
                return i; // 如果连通，返回当前时间
            }
        }
    }
    return -1; // 如果始终未连通，返回 -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) {
        this.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); // 将 p 的根节点连接到 q 的根节点下
    }
}

例题二

1. 题目链接：省份数量
2. 题目描述：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。

3. 示例：

4. 算法思路：

1. 理解问题 省份：一组直接或间接相连的城市，组内不含其他没有相连的城市。 目标：统计这些省份的数量。
2. 使用并查集 并查集是一种用于管理不相交集合的数据结构，特别适合处理动态连通性问题。它支持两个主要操作： Find：确定某个元素属于哪个集合。 Union：将两个元素所在的集合合并。 在这个问题中，我们可以将每个城市视为一个元素，通过并查集来动态维护城市之间的连通性。
3. 初始化并查集 创建一个并查集，包含 n 个城市。 初始时，每个城市是一个独立的集合，每个城市的父节点指向自己，秩为 0。
4. 遍历矩阵并合并城市 遍历矩阵 isConnected，对于每对直接相连的城市（isConnected[i][j] == 1），使用并查集的 union 操作将它们合并到同一个集合中。 通过 union 操作，我们可以动态地维护城市之间的连通性。
5. 统计连通分量的数量 每次成功合并两个集合时，连通分量的数量减 1。 最终，连通分量的数量即为省份的数量。

5. 代码示例：

// 计算省份数量（连接分量数量）
public int findCircleNum(int[][] isConnected) {
    // 边界检查：如果矩阵为空，返回 0
    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++) {
            // 如果城市 i 和城市 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;               // 初始时每个城市都是独立的省份

        // 初始化每个节点的父节点为自己，秩为 1
        for (int i = 0; i < size; i++) {
            root[i] = i;    // 每个节点初始时是自己的根节点
            rank[i] = 1;    // 每个节点初始秩为 1
        }
    }

    // 查找节点的根节点（带路径压缩优化）
    public int find(int x) {
        // 如果 x 是根节点，直接返回
        if (x == root[x]) {
            return x;
        }
        // 路径压缩：将查找路径上的所有节点直接连接到根节点
        return root[x] = find(root[x]);
    }

    // 合并两个节点所在的集合
    public void union(int x, int y) {
        // 找到 x 和 y 的根节点
        int rootX = find(x);
        int rootY = find(y);

        // 如果两个节点不在同一集合中
        if (rootX != rootY) {
            // 按秩合并：将较小的树合并到较大的树下
            if (rank[rootX] > rank[rootY]) {
                // X 的秩更大，将 Y 的根节点连接到 X 的根节点下
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                // Y 的秩更大，将 X 的根节点连接到 Y 的根节点下
                root[rootX] = rootY;
            } else {
                // 秩相等，任选一个作为根节点，并将其秩加 1
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
            // 合并后连通分量数量减 1
            count--;
        }
    }

    // 获取当前连通分量的数量
    public int getCount() {
        return count;
    }
}

总结

本文介绍了并查集这一数据结构及其相关常用方法，并通过两道例题展示了并查集在具体算法中的应用。