LeetCode并查集算法全解析：从基础到高级应用

安全风信子

发布于 2025-11-13 15:27:55

1200

文章被收录于专栏：AI SPPECHAI SPPECH

一、并查集基础概念

1.1 并查集的定义

并查集（Union-Find）是一种树形的数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种主要操作：

查找（Find）：确定某个元素属于哪个集合，通常是返回该集合的代表元素
合并（Union）：将两个集合合并成一个集合

并查集常用于解决诸如网络连接、社交网络分组、最小生成树等问题。

1.2 并查集的基本实现

并查集的基本实现需要一个数组来表示每个元素的父节点。初始时，每个元素的父节点是它自己，表示每个元素初始时属于单独的集合。

以下是并查集的基本实现：

class UnionFind {
    private int[] parent; // 存储每个元素的父节点
    
    // 初始化并查集，每个元素的父节点是它自己
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // 查找元素x所在的集合的代表元素（即根节点）
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    // 合并元素x和元素y所在的集合
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
    
    // 判断元素x和元素y是否属于同一个集合
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

1.3 并查集的优化技巧

并查集有两种常见的优化技巧：

路径压缩（Path Compression）：在查找操作中，将查找路径上的所有节点直接连接到根节点，从而减少后续查找的深度。
按秩合并（Union by Rank）：在合并操作中，将较小的树连接到较大的树上，从而减少树的高度。这里的"秩"通常指树的高度或大小。

以下是带有路径压缩和按秩合并优化的并查集实现：

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] = 1; // 初始时，每个树的高度都是1
        }
    }
    
    // 查找元素x所在的集合的代表元素（带路径压缩）
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    // 合并元素x和元素y所在的集合（按秩合并）
    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]++;
            }
        }
    }
    
    // 判断元素x和元素y是否属于同一个集合
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

1.4 并查集的时间复杂度

经过路径压缩和按秩合并优化后，并查集的时间复杂度接近于 O(1)。更精确地说，对于 n 个元素进行 m 次操作，时间复杂度为 O(m·α(n))，其中 α(n) 是阿克曼函数的反函数，在实际应用中，α(n) 的值非常小，可以视为常数。

二、并查集的经典问题解析

2.1 朋友圈（LeetCode 547）

题目描述：班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N×N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例：输入： [ [1,1,0], [1,1,0], [0,0,1] ] 输出：2 解释：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。学生 2 自己在一个朋友圈。所以返回 2。

解题思路

这是一个典型的并查集问题。我们可以将每个学生看作一个元素，将朋友关系看作是集合的合并操作。

具体步骤如下：

初始化一个大小为 N 的并查集，每个学生初始时属于单独的集合
遍历矩阵 M，如果 M[i][j] = 1，则合并学生 i 和学生 j 所在的集合
最后，统计并查集中集合的数量，即为朋友圈的总数

public int findCircleNum(int[][] M) {
    int n = M.length; // 学生的数量
    UnionFind uf = new UnionFind(n); // 初始化并查集
    
    // 遍历矩阵，合并朋友关系
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (M[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }
    
    // 统计朋友圈的数量（即集合的数量）
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (uf.find(i) == i) {
            count++;
        }
    }
    
    return count;
}

// 并查集类的定义（带路径压缩和按秩合并）
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] = 1;
        }
    }
    
    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]++;
            }
        }
    }
}

时间复杂度：O(n²·α(n))，其中 n 是学生的数量，α(n) 是阿克曼函数的反函数，可以视为常数。我们需要遍历 n×n 的矩阵，并进行 n² 次并查集操作。 空间复杂度：O(n)，需要存储并查集的 parent 数组和 rank 数组。

2.2 省份数量（LeetCode 547）

题目描述：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

示例：输入：isConnected = [ [1,1,0], [1,1,0], [0,0,1] ] 输出：2

解题思路

这道题与朋友圈问题完全相同，只是换了一个场景描述。我们可以使用并查集来解决。

具体步骤如下：

初始化一个大小为 n 的并查集，每个城市初始时属于单独的集合
遍历矩阵 isConnected，如果 isConnected[i][j] = 1，则合并城市 i 和城市 j 所在的集合
最后，统计并查集中集合的数量，即为省份的数量

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length; // 城市的数量
    UnionFind uf = new UnionFind(n); // 初始化并查集
    
    // 遍历矩阵，合并相连的城市
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }
    
    // 统计省份的数量（即集合的数量）
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (uf.find(i) == i) {
            count++;
        }
    }
    
    return count;
}

// 并查集类的定义（带路径压缩和按秩合并）
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] = 1;
        }
    }
    
    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]++;
            }
        }
    }
}

时间复杂度：O(n²·α(n))，其中 n 是城市的数量，α(n) 是阿克曼函数的反函数，可以视为常数。我们需要遍历 n×n 的矩阵，并进行 n² 次并查集操作。 空间复杂度：O(n)，需要存储并查集的 parent 数组和 rank 数组。

2.3 冗余连接（LeetCode 684）

题目描述：在本问题中，树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着 N 个节点（节点值不重复 1, 2, …, N）的树及一条附加的边构成。附加的边的两个顶点包含在原树中是不同的顶点。

请找出一条可以删去的边，使得结果图是一个有着 N 个节点的树。如果有多个答案，则返回二维数组中最后出现的边。

示例：输入：edges = [[1,2], [1,3], [2,3]] 输出：[2,3] 解释：给定的无向图为： 1 / 2 - 3

解题思路

这道题可以使用并查集来解决。我们可以将每条边视为两个节点的合并操作，如果在合并之前，这两个节点已经属于同一个集合，那么这条边就是冗余的边，因为它会导致环的形成。

具体步骤如下：

初始化一个大小为 N+1 的并查集（节点值从 1 开始）
遍历所有边，对于每条边 (u, v)：
- 如果 u 和 v 已经属于同一个集合，那么这条边就是冗余的边，返回它
- 否则，合并 u 和 v 所在的集合
如果遍历结束后没有找到冗余的边，则返回空数组

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length; // 节点的数量（节点值为 1 到 n）
    UnionFind uf = new UnionFind(n + 1); // 初始化并查集，索引从 1 开始
    
    // 遍历所有边
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        // 如果 u 和 v 已经属于同一个集合，那么这条边就是冗余的边
        if (uf.isConnected(u, v)) {
            return edge;
        }
        // 否则，合并 u 和 v 所在的集合
        uf.union(u, v);
    }
    
    return new int[0]; // 不应该到达这里
}

// 并查集类的定义（带路径压缩和按秩合并）
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] = 1;
        }
    }
    
    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]++;
            }
        }
    }
    
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

时间复杂度：O(n·α(n))，其中 n 是节点的数量，α(n) 是阿克曼函数的反函数，可以视为常数。我们需要遍历 n 条边，并进行 n 次并查集操作。 空间复杂度：O(n)，需要存储并查集的 parent 数组和 rank 数组。

2.4 岛屿数量（LeetCode 200）

题目描述：给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例：输入：grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“0”,“0”,“0”] ] 输出：1

输入：grid = [ [“1”,“1”,“0”,“0”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“1”,“0”,“0”], [“0”,“0”,“0”,“1”,“1”] ] 输出：3

解题思路

这道题可以使用DFS或BFS来解决，但我们也可以使用并查集来解决。我们可以将每个陆地格子看作一个元素，将相邻的陆地格子合并到同一个集合中。

具体步骤如下：

初始化一个并查集，每个陆地格子初始时属于单独的集合
遍历网格中的每个格子，如果当前格子是陆地，检查其上方和左方的格子是否也是陆地，如果是，则合并这两个格子所在的集合
最后，统计并查集中集合的数量，即为岛屿的数量

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    
    int m = grid.length;    // 网格的行数
    int n = grid[0].length; // 网格的列数
    int count = 0;          // 陆地格子的数量
    
    // 计算陆地格子的数量
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                count++;
            }
        }
    }
    
    UnionFind uf = new UnionFind(m * n); // 初始化并查集
    
    // 定义四个方向的偏移量（上、右、下、左）
    int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    // 遍历网格中的每个格子
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                // 将当前格子标记为已访问
                grid[i][j] = '0';
                
                // 检查四个方向的相邻格子
                for (int[] dir : directions) {
                    int newRow = i + dir[0];
                    int newCol = j + dir[1];
                    // 如果相邻格子在网格范围内且是陆地，则合并这两个格子所在的集合
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == '1') {
                        uf.union(i * n + j, newRow * n + newCol);
                        count--; // 每合并一次，陆地格子的数量减1
                    }
                }
            }
        }
    }
    
    return count;
}

// 并查集类的定义（带路径压缩和按秩合并）
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] = 1;
        }
    }
    
    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]++;
            }
        }
    }
}

时间复杂度：O(m·n·α(m·n))，其中 m 和 n 分别是网格的行数和列数，α(m·n) 是阿克曼函数的反函数，可以视为常数。我们需要遍历 m×n 的网格，并进行 m×n 次并查集操作。 空间复杂度：O(m·n)，需要存储并查集的 parent 数组和 rank 数组。

三、并查集的进阶问题

3.1 冗余连接 II（LeetCode 685）

题目描述：在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着 N 个节点（节点值不重复 1, 2, …, N）的树及一条附加的有向边构成。附加的边的两个顶点包含在原树中是不同的顶点。

请找出一条可以删去的边，使得结果图是一个有着 N 个节点的有根树。如果有多个答案，则返回二维数组中最后出现的边。

示例：输入：edges = [[1,2], [1,3], [2,3]] 输出：[2,3]

输入：edges = [[1,2], [2,3], [3,4], [4,1], [1,5]] 输出：[4,1]

解题思路

这道题是冗余连接的升级版，处理的是有向图。在有向图中，可能存在两种情况导致图不是一棵树：

存在一个节点有两个父节点
存在一个环

我们可以使用并查集来解决这个问题。具体步骤如下：

首先，检查是否存在一个节点有两个父节点，如果有，记录这两条边
如果存在这样的节点，尝试删除其中一条边，然后检查剩余的边是否能构成一棵树
如果不存在这样的节点，说明图中存在一个环，我们需要找到构成环的边并删除它

public int[] findRedundantDirectedConnection(int[][] edges) {
    int n = edges.length; // 节点的数量（节点值为 1 到 n）
    int[] inDegree = new int[n + 1]; // 记录每个节点的入度
    int[] parent = new int[n + 1];   // 记录每个节点的父节点
    int[] candidate1 = null;         // 第一条导致节点有两个父节点的边
    int[] candidate2 = null;         // 第二条导致节点有两个父节点的边
    
    // 初始化 parent 数组
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    // 检查是否存在一个节点有两个父节点
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        inDegree[v]++;
        if (inDegree[v] == 2) {
            // 找到了一个有两个父节点的节点
            candidate1 = edge;
            // 找到该节点的另一个父节点
            for (int[] e : edges) {
                if (e[1] == v && !Arrays.equals(e, edge)) {
                    candidate2 = e;
                    break;
                }
            }
            break;
        }
    }
    
    // 如果存在一个节点有两个父节点，尝试删除其中一条边
    if (candidate1 != null) {
        // 尝试删除 candidate1
        if (isTreeAfterRemoveEdge(edges, candidate1)) {
            return candidate1;
        }
        // 尝试删除 candidate2
        return candidate2;
    }
    
    // 否则，图中存在一个环，使用并查集找到构成环的边
    UnionFind uf = new UnionFind(n + 1);
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        if (uf.isConnected(u, v)) {
            return edge;
        }
        uf.union(u, v);
    }
    
    return new int[0]; // 不应该到达这里
}

// 检查删除一条边后，剩余的边是否能构成一棵树
private boolean isTreeAfterRemoveEdge(int[][] edges, int[] edgeToRemove) {
    int n = edges.length;
    UnionFind uf = new UnionFind(n + 1);
    int count = n; // 初始时，每个节点都是一个单独的集合
    
    for (int[] edge : edges) {
        if (Arrays.equals(edge, edgeToRemove)) {
            continue;
        }
        int u = edge[0];
        int v = edge[1];
        if (!uf.isConnected(u, v)) {
            uf.union(u, v);
            count--;
        } else {
            return false; // 存在环，不是树
        }
    }
    
    return count == 1; // 树有且仅有一个根节点
}

// 并查集类的定义（带路径压缩和按秩合并）
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] = 1;
        }
    }
    
    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]++;
            }
        }
    }
    
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

3.2 最长连续序列（LeetCode 128）

题目描述：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

解题思路

这道题可以使用并查集来解决。我们可以将每个整数看作一个元素，并将连续的整数合并到同一个集合中。

具体步骤如下：

初始化一个并查集，每个整数初始时属于单独的集合
使用一个哈希表来记录每个整数在并查集中的索引
遍历数组中的每个整数，如果该整数的前一个数或后一个数已经在哈希表中，则合并这两个数所在的集合
最后，统计并查集中最大的集合的大小，即为最长连续序列的长度

public int longestConsecutive(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int n = nums.length;
    UnionFind uf = new UnionFind(n); // 初始化并查集
    Map<Integer, Integer> numToIndex = new HashMap<>(); // 记录每个整数在并查集中的索引
    
    // 遍历数组中的每个整数
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        // 如果该整数已经在哈希表中，跳过
        if (numToIndex.containsKey(num)) {
            continue;
        }
        // 将该整数添加到哈希表中
        numToIndex.put(num, i);
        // 如果该整数的前一个数已经在哈希表中，合并这两个数所在的集合
        if (numToIndex.containsKey(num - 1)) {
            uf.union(i, numToIndex.get(num - 1));
        }
        // 如果该整数的后一个数已经在哈希表中，合并这两个数所在的集合
        if (numToIndex.containsKey(num + 1)) {
            uf.union(i, numToIndex.get(num + 1));
        }
    }
    
    // 统计并查集中最大的集合的大小
    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        if (uf.find(i) == i) {
            maxLength = Math.max(maxLength, uf.getSize(i));
        }
    }
    
    return maxLength;
}

// 并查集类的定义（带路径压缩和按秩合并，以及获取集合大小的功能）
class UnionFind {
    private int[] parent;
    private int[] rank;
    private int[] size; // 记录每个集合的大小
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
            size[i] = 1;
        }
    }
    
    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;
                size[rootX] += size[rootY];
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
                size[rootX] += size[rootY];
            }
        }
    }
    
    public int getSize(int x) {
        return size[find(x)];
    }
}

时间复杂度：O(n·α(n))，其中 n 是数组的长度，α(n) 是阿克曼函数的反函数，可以视为常数。我们需要遍历 n 个元素，并进行 n 次并查集操作。 空间复杂度：O(n)，需要存储并查集的 parent 数组、rank 数组和 size 数组，以及哈希表。

3.3 由斜杠划分区域（LeetCode 959）

题目描述：在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些区域。

请注意，反斜杠字符是转义的，因此用 “\” 表示。例如，“/\” 表示方块中有一个 / 字符和一个 \ 字符。

返回区域的总数。

示例：输入： [ " /", "/ " ] 输出：2

输入： [ " /", " " ] 输出：1

解题思路

这道题可以使用并查集来解决。我们可以将每个 1x1 的方块分成四个小三角形，然后根据方块中的字符类型，合并相应的小三角形。

具体步骤如下：

将每个 1x1 的方块分成四个小三角形（上、右、下、左）
初始化一个大小为 4NN 的并查集
对于每个方块，根据其中的字符类型，合并相应的小三角形
同时，合并相邻方块的小三角形（左边方块的右小三角形和右边方块的左小三角形，上边方块的下小三角形和下边方块的上小三角形）
最后，统计并查集中集合的数量，即为区域的总数

public int regionsBySlashes(String[] grid) {
    int n = grid.length; // 网格的大小
    int size = 4 * n * n; // 并查集的大小（每个方块分成4个小三角形）
    UnionFind uf = new UnionFind(size); // 初始化并查集
    
    // 遍历每个方块
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int index = 4 * (i * n + j); // 当前方块的第一个小三角形的索引
            char c = grid[i].charAt(j);
            
            // 根据方块中的字符类型，合并相应的小三角形
            if (c == ' ') {
                // 空格：四个小三角形合并成一个区域
                uf.union(index, index + 1);
                uf.union(index + 1, index + 2);
                uf.union(index + 2, index + 3);
            } else if (c == '/') {
                // / 字符：合并上、左小三角形，合并右、下小三角形
                uf.union(index, index + 3);
                uf.union(index + 1, index + 2);
            } else if (c == '\\') {
                // \ 字符：合并上、右小三角形，合并左、下小三角形
                uf.union(index, index + 1);
                uf.union(index + 2, index + 3);
            }
            
            // 合并相邻方块的小三角形（右边的方块）
            if (j + 1 < n) {
                uf.union(index + 1, 4 * (i * n + j + 1) + 3);
            }
            
            // 合并相邻方块的小三角形（下边的方块）
            if (i + 1 < n) {
                uf.union(index + 2, 4 * ((i + 1) * n + j));
            }
        }
    }
    
    // 统计区域的数量（即集合的数量）
    int count = 0;
    for (int i = 0; i < size; i++) {
        if (uf.find(i) == i) {
            count++;
        }
    }
    
    return count;
}

// 并查集类的定义（带路径压缩和按秩合并）
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] = 1;
        }
    }
    
    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]++;
            }
        }
    }
}

时间复杂度：O(n²·α(n²))，其中 n 是网格的大小，α(n²) 是阿克曼函数的反函数，可以视为常数。我们需要遍历 n×n 的网格，并进行 n² 次并查集操作。 空间复杂度：O(n²)，需要存储并查集的 parent 数组和 rank 数组。

3.4 最小生成树 - Kruskal 算法（LeetCode 1135）

题目描述：想象一下你是个城市基建规划者，地图上有 n 个城市，它们按以 1 到 n 的次序编号。给你连接两个城市的可能路线，形式为 cost[i] = [A, B, COST]，表示从城市 A 到城市 B 需要花费 COST。

你需要以最低的成本连接所有城市，返回所有城市连通所需要的最低成本。如果无法连接所有城市，则返回 -1。

示例：输入：n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]] 输出：6 解释：选择城市 1 和城市 2，成本为 5；选择城市 2 和城市 3，成本为 1。总成本为 6。

解题思路

这道题可以使用 Kruskal 算法来解决，而 Kruskal 算法的核心就是并查集。Kruskal 算法的基本思想是：

将所有边按权重从小到大排序
依次考察每条边，如果这条边连接的两个顶点不在同一个连通分量中，则选择这条边，并将这两个顶点所在的连通分量合并
重复步骤 2，直到选择了 n-1 条边（n 是顶点的数量）

具体步骤如下：

将所有边按权重从小到大排序
初始化一个大小为 n+1 的并查集（顶点编号从 1 开始）
依次考察每条边，如果这条边连接的两个顶点不在同一个连通分量中，则选择这条边，并将这两个顶点所在的连通分量合并
当选择了 n-1 条边后，所有顶点都已经连通，返回总成本
如果遍历完所有边后，选择的边数少于 n-1，则无法连接所有顶点，返回 -1

public int minimumCost(int n, int[][] connections) {
    // 将所有边按权重从小到大排序
    Arrays.sort(connections, Comparator.comparingInt(a -> a[2]));
    
    UnionFind uf = new UnionFind(n + 1); // 初始化并查集，顶点编号从 1 开始
    int totalCost = 0;                   // 总成本
    int edgeCount = 0;                   // 已选择的边的数量
    
    // 依次考察每条边
    for (int[] connection : connections) {
        int u = connection[0];
        int v = connection[1];
        int cost = connection[2];
        
        // 如果这条边连接的两个顶点不在同一个连通分量中，则选择这条边
        if (!uf.isConnected(u, v)) {
            uf.union(u, v);
            totalCost += cost;
            edgeCount++;
            
            // 当选择了 n-1 条边后，所有顶点都已经连通，返回总成本
            if (edgeCount == n - 1) {
                return totalCost;
            }
        }
    }
    
    // 如果遍历完所有边后，选择的边数少于 n-1，则无法连接所有顶点
    return -1;
}

// 并查集类的定义（带路径压缩和按秩合并）
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] = 1;
        }
    }
    
    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]++;
            }
        }
    }
    
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

时间复杂度：O(m·log m + m·α(n))，其中 m 是边的数量，n 是顶点的数量，α(n) 是阿克曼函数的反函数，可以视为常数。我们需要对 m 条边进行排序，然后进行 m 次并查集操作。 空间复杂度：O(n)，需要存储并查集的 parent 数组和 rank 数组。

四、并查集的优化技巧总结

4.1 路径压缩优化

路径压缩是并查集的一种重要优化技巧，它可以显著减少查找操作的时间复杂度。在查找操作中，路径压缩将查找路径上的所有节点直接连接到根节点，从而减少后续查找的深度。

路径压缩有两种常见的实现方式：

完全路径压缩：在查找操作中，将查找路径上的所有节点直接连接到根节点

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 递归实现，完全路径压缩
    }
    return parent[x];
}

路径分裂：在查找操作中，将查找路径上的每个节点的父节点设置为其祖父节点

public int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // 路径分裂
        x = parent[x];
    }
    return x;
}

4.2 按秩合并优化

按秩合并是并查集的另一种重要优化技巧，它可以控制树的高度，从而减少查找操作的时间复杂度。在合并操作中，按秩合并将较小的树连接到较大的树上。

按秩合并有两种常见的实现方式：

按高度合并：使用树的高度作为秩，将高度较小的树连接到高度较大的树上

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

按大小合并：使用树的大小（节点数量）作为秩，将大小较小的树连接到大小较大的树上

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (size[rootX] > size[rootY]) {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        } else {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
    }
}

4.3 并查集的扩展功能

除了基本的查找和合并操作外，我们还可以为并查集添加一些扩展功能，以满足不同问题的需求：

获取集合的大小：在合并操作时，维护每个集合的大小

public int getSize(int x) {
    return size[find(x)];
}

获取集合的数量：在初始化时，集合的数量等于元素的数量；在合并操作时，每合并一次，集合的数量减1

public int getCount() {
    return count;
}

记录每个元素到根节点的距离：在查找和合并操作时，维护每个元素到根节点的距离

public int find(int x) {
    if (parent[x] != x) {
        int root = find(parent[x]);
        distance[x] += distance[parent[x]]; // 累加距离
        parent[x] = root;
    }
    return parent[x];
}