Leetcode --- 并查集相关题目

写在前：并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：

• Find（查找）：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union（合并）：将两个子集合并成同一个集合。

ps：这里的集合也可叫连通块（连通分量），典型应用解决连通分量问题。

并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1)，可以应用在在线算法中。

路径压缩算法：即查找过程，最理想的情况就是所有点的代表节点都是相同，一共就是两级结构。做法就是在查找时找到根之后把自身的值修改成根的下标，可以通过递归和迭代实现。

路径压缩

1.冗余连接（684 - 中）

题目描述：在本问题中, 树指的是一个连通且无环的无向图。输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 :

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
    |   |
    4 - 3

思路：树是一个连通并无环的无向图，如果一棵树有 N个节点，则这棵树有 N-1条边。初始化N个节点，每个节点属于不同的集合。

可以通过并查集寻找附加的边，本质是检测图的环。如果边的两个节点已经出现在同一个集合里（在合并之前已经连通），说明着边的两个节点已经连在一起了，如果再加入这条边一定就出现环了，记录并返回。

代码实现：

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length + 1;
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.ans;
    }
}

class UnionFind {
    int[] roots;
    int[] ans = new int[2];  // 存放结果集

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

    public int find(int i) {
        if (i != roots[i]) {
            roots[i] = find(roots[i]);
        }
        return roots[i];
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
        } else {
            ans[0] = p;
            ans[1] = q;
        }
    }
}

2.省份数量（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，则初始化 n 个单顶点集合，每个集合指向自身。

• 然后遍历图中的每个顶点，将当前顶点与其邻接点进行合并。

• 最终结果返回合并后的集合的数量即可。

代码实现：

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        // 初始化n个单顶点集合，
        UnionFind uf = new UnionFind(n);
        // 遍历一半矩阵（两个城市単连接即可），遇到1连接两个城市
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.size;
    }
}

class UnionFind {
    int[] roots;   // 记录每个省份的核心城市
    int size;   // 集合的数量

    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
        size = n;
    }
    // 寻找当前城市所在省份（城市群）的核心城市
    public int find(int i) {
        //若当前城市不是核心城市，则递归更新（类似树结构）
        if (i != roots[i]) {
            roots[i] = find(roots[i]);
        }
        return roots[i];
    }
    // 将两个城市连接到一个省份
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        // 当两个城市的核心城市不同时，连接并更新核心城市，集合数量-1；若两个城市在同一省份则不减
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
            size--;
        }
    }
}

3.被围绕的区域（130 - 中）

题目描述：给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充，返回填充后的矩阵。

示例 :

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

思路：本题中O本质就是两大类：一种可以连通到边界，一种不能连通到边界（需要X覆盖）。

• 并查集就是解决一种分类（连通性）问题的。对于每个节点我们用行数和列数生成id进行标识（用于下一步）。
• 遍历每个O节点，上下左右四个方向进行合并：定义dummy节点区分上述两大分类（将连通到边界的与dummy进行合并）。
  • 如果当前O在边界，先与dummy节点合并
  • 否则将当前点与上下左右O进行合并
• 再遍历矩阵，只需要判断O节点是否与dummy节点连通，如不连通则替换为X。

代码实现：

class Solution {
    int row, col;
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        row = board.length;
        col = board[0].length;
        int dummy = row * col;  // 虚拟分类点
        UnionFind uf = new UnionFind(row * col + 1);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    //当前节点在边界就和 dummy 合并
                    if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
                        uf.union(dummy, node(i, j));
                    } else {
                        //将上下左右的 O 节点和当前节点合并
                        if (board[i - 1][j] == 'O') uf.union(node(i, j), node(i - 1, j));
                        if (board[i][j - 1] == 'O') uf.union(node(i, j), node(i, j - 1));
                        if (board[i + 1][j] == 'O') uf.union(node(i, j), node(i + 1, j));
                        if (board[i][j + 1] == 'O') uf.union(node(i, j), node(i, j + 1));
                    }
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (uf.isConnected(node(i, j), dummy)) {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }
    
    int node(int i, int j) {
        return i * col + j;
    }
}

class UnionFind {
    int[] roots;

    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }
    
    public int find(int i) {
        while (i != roots[i]) {
            roots[i] = roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
        }
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

ps：这里并查集的效率有点低。

4.岛屿的数量（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

思路：使用并查集计算集合（岛屿）的数量。对于陆地情况可以上下左右进行查找。类似547省份数量，用size变量保存连通分量的数量

注意：最终size = 连通块的个数 + 水的元素个数

• 故在遍历每个元素的时候，统计水的个数（0的个数）
• 岛屿数量 = size - 水的个数

代码实现：

class Solution {
    public int row, col;
    public int numIslands(char[][] grid) {
        row = grid.length;
        col = grid[0].length;
        int n = row * col;
        int ocean = 0;
        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0') {
                    ocean += 1;
                } else {
                    if (i > 0 && grid[i - 1][j] == '1') uf.union(node(i, j), node(i - 1, j));
                    if (j > 0 && grid[i][j - 1] == '1') uf.union(node(i, j), node(i, j - 1));
                    if (i < row - 1 && grid[i + 1][j] == '1') uf.union(node(i, j), node(i + 1, j));
                    if (j < col - 1 && grid[i][j + 1] == '1') uf.union(node(i, j), node(i, j + 1));
                }
            }
        }
        return uf.size - ocean;
    }
    int node (int i, int j) {
        return i * col + j;
    }
}

class UnionFind {
    int[] roots;
    int size;   // 岛屿数量

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

    public int find(int i) {
        while (i != roots[i]) {
            roots[i] =roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
            size--;
        }
    }
}

5.移除最多的同行或同列石头（947 - 中）

题目描述：如果想移除一个石头，那么它所在的行或者列必须有其他石头存在。我们能移除的最多石头数是多少？也就是说，只有一个石头在连通分量中，才能被移除。对于连通分量而言，最理想的状态是只剩一块石头。对于任何容量为n（n>1）一个连通分量，可以移除的石头数都为n-1。

示例 :

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。

思路：本题注意理解我们要删除最多的石头（最后返回值），为此我们将所有的行和列进行连接呢？

• 在图上构建若干个集合，每个集合可以看成一个钥匙串，最后每个钥匙串至少剩下一个钥匙。一个核心（尽可能多删除）
• 并查集里的元素是 描述「横坐标」和「纵坐标」的数值。
• 假设有M个集合，设总结点数为N，那么显而易见，我们能够删除的总结点数，也即move数为：move = N - M；

在原始的输入中，行标号和列标号是共用的[1,n]区间内的数字，导致行值和列值重复，无法达到我们完成并查集的结点连接的目的。

• 根据题目给出的数据范围，单个坐标数值小于10000。

• 将列值映射到[10000,10000+n]的区间内，这样我们就获得了所有节点的标号。

代码实现：

class Solution {
    public int removeStones(int[][] stones) {
        int size = stones.length;
        // 题目给的数值在0 -10000，0-10000给横坐标，10001-20002留给纵坐标
        UnionFind uf = new UnionFind(20002);
        for (int i = 0; i < size; i++) {
            uf.union(stones[i][0], stones[i][1] + 10001);
        }

        // 统计集合个数（即roots数量），由于行列为同一roots，故统计一个即可
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < size; i++) {
            set.add(uf.find(stones[i][0]));
        }
        // 总石头数量 - roots数量 == 最多可以删除的节点数
        return size - set.size();
    }
}

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

    public int find(int i) {
        while (i != roots[i]) {
            roots[i] = roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
        }
    }
}

6.连通网络的操作次数（1319 - 中）

题目描述：用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

示例 :

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

思路：最终实现目标：将所有网络连接成同一个网络。类似547省份问题。注意两个问题：

• 线要够，即n个节点至少需要n-1条线
• 三个连通块至少需要两个边（即需要两条多余的线），问题转化为：最少操作数（多余线缆）= 连通块数量 - 1

代码实现：

class Solution {
    public int makeConnected(int n, int[][] connections) {
        int num = connections.length;
        if (num < n - 1) return -1;  // 线不够
        UnionFind uf = new UnionFind(n);
        
        for (int[] connection : connections) {
            uf.union(connection[0], connection[1]);
        }
        return uf.count - 1;   
    }
}

class UnionFind {
    int[] roots;
    int count;  // 记录连通块的数量
    
    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
        count = n;  
    }

    public int find(int i) {
        while (i != roots[i]) {
            roots[i] = roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
            count--;   
        }
    }
}