使用并查集解决的相关问题

作者: Grey

原文地址：

博客园：使用并查集解决的相关问题

CSDN：使用并查集解决的相关问题

关于并查集的说明，见如下博客：

使用并查集处理集合的合并和查询问题

相关题目

LeetCode 200. 岛屿数量

本题的解题思路参考博客

使用DFS和并查集方法解决岛问题

LeetCode 547. 省份数量

主要思路

横纵坐标表示的是城市，因为城市是一样的，所以只需要遍历对角线上半区或者下半区即可，如果某个(i,j)位置是1，可以说明如下两个情况

第一，i这座城市和j这座城市可以做union操作。

第二，(j,i)位置一定也是1。

遍历完毕后，返回整个并查集中的集合数量即可。

完整代码

public static int findCircleNum(int[][] m) {
        int n = m.length;
        UF uf = new UF(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);
                }
            }
        }
        return uf.setSize();
    }

    public static class UF {
        int[] parent;
        int[] help;
        int[] size;
        int sets;

        public UF(int n) {
            size = new int[n];
            parent = new int[n];
            help = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
            sets = n;
        }

        public void union(int i, int j) {
            if (i == j) {
                return;
            }
            int p1 = find(i);
            int p2 = find(j);
            if (p2 != p1) {
                int size1 = size[p1];
                int size2 = size[p2];
                if (size1 > size2) {
                    parent[p2] = p1;
                    size[p1] += size2;
                } else {
                    parent[p1] = p2;
                    size[p2] += size1;
                }
                sets--;
            }
        }

        public int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (int index = 0; index < hi; index++) {
                parent[help[index]] = i;
            }
            return i;
        }

        public int setSize() {
            return sets;
        }
    }

LeetCode 305. 岛屿数量II

本题和LeetCode 200. 岛屿数量最大的区别就是，本题是依次给具体的岛屿，并查集要实时union合适的两个岛屿，思路也一样，初始化整个地图上都是水单元格，且整个地图的岛屿数量初始为0，如果某个位置来一个岛屿，先将此位置的代表节点设置为本身，将此位置的集合大小设置为1，然后和其上下左右方向有岛屿的点union一下，并将集合数量减一，返回集合数量即可，完整代码见：

    public static List<Integer> numIslands2(int m, int n, int[][] positions) {
        UF uf = new UF(m, n);
        List<Integer> ans = new ArrayList<>();
        for (int[] position : positions) {
            ans.add(uf.connect(position[0], position[1]));
        }
        return ans;
    }

    public static class UF {
        int[] help;
        int[] parent;
        int[] size;
        int sets;
        int row;
        int col;

        public UF(int m, int n) {
            row = m;
            col = n;
            int len = m * n;
            help = new int[len];
            size = new int[len];
            parent = new int[len];
        }


        private int index(int i, int j) {
            return i * col + j;
        }

        private void union(int i1, int j1, int i2, int j2) {
            if (i1 < 0 || i2 < 0 || i1 >= row || i2 >= row || j1 < 0 || j2 < 0 || j1 >= col || j2 >= col) {
                return;
            }

            int f1 = index(i1, j1);
            int f2 = index(i2, j2);
            if (size[f1] == 0 || size[f2] == 0) {
                // 重要：如果两个都不是岛屿，则不用合并
                return;
            }
            f1 = find(f1);
            f2 = find(f2);
            if (f1 != f2) {
                int s1 = size[f1];
                int s2 = size[f2];
                if (s1 >= s2) {
                    size[f1] += s2;
                    parent[f2] = f1;
                } else {
                    size[f2] += s1;
                    parent[f1] = f2;
                }
                sets--;
            }
        }

        public int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (int index = 0; index < hi; index++) {
                parent[help[index]] = i;
            }
            return i;
        }

        public int connect(int i, int j) {
            int index = index(i, j);
            if (size[index] == 0) {
                sets++;
                size[index] = 1;
                parent[index] = index;
                // 去四个方向union
                union(i - 1, j, i, j);
                union(i, j - 1, i, j);
                union(i + 1, j, i, j);
                union(i, j + 1, i, j);
            }
            // index上本来就有岛屿，所以不需要处理
            return sets;
        }
    }

类似问题：LintCode 434. 岛屿的个数II

LeetCode 130. 被围绕的区域

和LeetCode 200. 岛屿数量问题一样，这个题目也有DFS和并查集两种解决方法。DFS方法的思路是，先遍历最外圈（即：第一行，第一列，最后一行，最后一列），最外圈中的元素如果为O，则做如下事情：

将这个元素和其相连的元素都设置为#号（或者其他的只要不是原矩阵有的字符），我们可以简单理解为，拿最外圈的O元素去"解救"和其相连的所有元素，并打上一个标记。

然后再次遍历整个矩阵，只要没打上标记的（理解为没被解救的），都设置为X，其余的都是O。

DFS解法的完整代码见：

    public static void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                free(i, 0, board);
            }
            if (board[i][n - 1] == 'O') {
                free(i, n - 1, board);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                free(0, i, board);
            }
            if (board[m - 1][i] == 'O') {
                free(m - 1, i, board);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = (board[i][j] != '#' ? 'X' : 'O');
            }
        }
    }
    
    public static void free(int i, int j, char[][] board) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        board[i][j] = '#';
        free(i + 1, j, board);
        free(i - 1, j, board);
        free(i, j + 1, board);
        free(i, j - 1, board);
    }

本题还有并查集的做法，即，将矩阵第一列，最后一列，第一行，最后一行中的所有O节点的代表节点都设置为dump节点，然后遍历矩阵的其他位置，只要是O字符的，就和其四个方向的节点进行union操作，最后，再次遍历整个矩阵，如果是O且和dump不是同一集合的，就算是没有被解救的点，否则，都设置为X。

完整代码如下：

public static void solve(char[][] board) {
        if (board == null || board.length <= 2 || board[0].length <= 2) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        // 所有周边为O的点的代表节点都设置为dump
        int dump = 0;
        UF uf = new UF(m, n);
    // 第一列和最后一列O字符的元素和dump点union一下
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                uf.union(dump, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                uf.union(dump, i, n - 1);
            }
        }
    // 第一行和最后一行O字符的元素和dump点union一下
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                uf.union(dump, 0, i);
            }
            if (board[m - 1][i] == 'O') {
                uf.union(dump, m - 1, i);
            }
        }
    // 其他位置，只要是O字符，就和上下左右的O字符union一下
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O') {
                    int index = uf.index(i, j);
                    if (board[i - 1][j] == 'O') {
                        uf.union(index, i - 1, j);
                    }
                    if (board[i][j - 1] == 'O') {
                        uf.union(index, i, j - 1);
                    }
                    if (board[i + 1][j] == 'O') {
                        uf.union(index, i + 1, j);
                    }
                    if (board[i][j + 1] == 'O') {
                        uf.union(index, i, j + 1);
                    }
                }
            }
        }
    // 最后判断哪些不是和dump点在同一集合的O点，这些都会被X吞没
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O' && !uf.isSameSet(dump, i, j)) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public static class UF {
        int[] help;
        int[] size;
        int[] parent;
        int row;
        int col;

        public UF(int m, int n) {
            row = m;
            col = n;
            // 多一个位置，用于存dump
            int len = m * n + 1;
            help = new int[len];
            size = new int[len];
            parent = new int[len];
            for (int i = 1; i < len; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int index(int i, int j) {
            return i * col + j + 1;
        }

        private int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (int index = 0; index < hi; index++) {
                parent[help[index]] = i;
            }
            return i;
        }

        public void union(int p1, int i, int j) {
            int p2 = index(i, j);
            int f1 = find(p1);
            int f2 = find(p2);
            if (f1 != f2) {
                int s1 = size[f1];
                int s2 = size[f2];
                if (s1 >= s2) {
                    size[f1] += s2;
                    parent[f2] = f1;
                } else {
                    size[f2] += s1;
                    parent[f1] = f2;
                }
            }
        }

        public boolean isSameSet(int p, int i, int j) {
            return find(p) == find(index(i, j));
        }
    }

类似问题：LintCode 477. 被围绕的区域

LintCode 178. 图是否是树

本题比较简单，判断条件如下：

1. 如果n等于0，默认就是空树，直接返回true

2. 如果n - 1 != 边数量，说明不是树，因为对于有n个点的树，边的数量一定是n-1。

3. 最重要的一个判断条件：如果一个边中的的两个点的代表节点一样，说明出现了环，所以，最后union掉所有边的所有节点，如果集合个数不等于1，说明有环，直接返回false。

完整代码见：

    public static boolean validTree(int n, int[][] edges) {
        if (n == 0) {
            return true;
        }
        if (n - 1 != edges.length) {
            return false;
        }
        LeetCode_0261_GraphValidTree.UnionFind uf = new LeetCode_0261_GraphValidTree.UnionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.setSize() == 1;
    }

    // 如何判断环？ 如果一个node节点中两个点的代表点一样，说明出现了环，直接返回false
    public static class UnionFind {
        private int[] parents;
        private int[] size;
        private int[] help;
        private int sets;

        public UnionFind(int n) {
            parents = new int[n];
            size = new int[n];
            help = new int[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
                size[i] = 1;
            }
            sets = n;
        }

        public int find(int i) {
            int hi = 0;
            while (i != parents[i]) {
                help[hi++] = i;
                i = parents[i];
            }
            for (int j = 0; j < hi; j++) {
                parents[help[j]] = i;
            }
            return i;

        }

        public void union(int i, int j) {
            int f1 = find(i);
            int f2 = find(j);
            if (f1 != f2) {
                int s1 = size[f1];
                int s2 = size[f2];
                if (s1 < s2) {
                    parents[f1] = parents[f2];
                    size[f2] += s1;
                } else {
                    parents[f2] = parents[f1];
                    size[f1] += s2;
                }
                sets--;
            }
        }

        public int setSize() {
            return sets;
        }
    }

类似问题：LeetCode 261. 以图判断树

LeetCode 952. 按公因数计算最大组件大小

本题关键解法也是并查集，只不过在union过程中，需要将当前位置的所有因数得到并先保存起来，我们可以用哈希表来保存这样的关系，以6个数为例，存在哈希表中有两条记录，即：

记录1: key：3，value：6

记录2： key： 2，value：6

当我来到下一个数的时候，如果这个数的因数有3，则我可以通过哈希表直接找到曾经有一个6和你有共同的因数。然后就可以把这个数和6进行union操作，最后只要返回并查集中集合元素最多的那个集合数量即可。完整代码如下：

    public static int largestComponentSize(int[] arr) {
        UnionFind uf = new UnionFind(arr.length);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            // 以下是找arr[i]有哪些因数的相对比较快的做法。
            int num = (int) Math.sqrt(arr[i]);
            for (int j = 1; j <= num; j++) {
                if (arr[i] % j == 0) {
                    if (j != 1) {
                        if (!map.containsKey(j)) {
                            map.put(j, i);
                        } else {
                            // 找到有共同因数的元素了，可以合并了
                            uf.union(map.get(j), i);
                        }
                    }
                    int other = arr[i] / j;
                    if (other != 1) {
                        if (!map.containsKey(other)) {
                            map.put(other, i);
                        } else {
                            // 找到有共同因数的元素了，可以合并了
                            uf.union(map.get(other), i);
                        }
                    }
                }
            }
        }
        return uf.maxSize();
    }

    // 并查集
    public static class UnionFind {
        private int[] parents;
        private int[] size;
        private int[] help;

        public UnionFind(int len) {
            parents = new int[len];
            size = new int[len];
            help = new int[len];
            for (int i = 0; i < len; i++) {
                parents[i] = i;
                size[i] = 1;
            }
        }

        public int maxSize() {
            int ans = 0;
            for (int size : size) {
                ans = Math.max(ans, size);
            }
            return ans;
        }

        private int find(int i) {
            int hi = 0;
            while (i != parents[i]) {
                help[hi++] = i;
                i = parents[i];
            }
            for (int j = 0; j < hi; j++) {
                parents[help[j]] = i;
            }
            return i;
        }

        // i 和 j分别是两个数的位置，不是值
        public void union(int i, int j) {
            int f1 = find(i);
            int f2 = find(j);
            if (f1 != f2) {
                int s1 = size[f1];
                int s2 = size[f2];
                if (s1 > s2) {
                    parents[f2] = f1;
                    size[f1] += s2;
                } else {
                    parents[f1] = f2;
                    size[f2] += s1;
                }
            }
        }
    }

LeetCode 803. 打砖块

主要思路

先做预处理，遍历整个矩阵，设置一个变量cellingAll，用来存连在天花板上1的数量，如果在1位置上设置了炮弹，那么将这个位置的值变成2，说明这个位置被打中了，如果在0值上设置了炮弹，就维持0，证明炮弹打空了。经过以上预处理后，

然后按打炮弹的顺序的相反顺序遍历，遇到2就变成1，然后以这个点作为分割点在看接到天花板1的数量的变化，如果前后的值没变化，说明打击没有使得砖块掉落，如果打击后使得接在天花板的砖块数量变多，则两次数量的差值减1即为这次击落的砖块数量。

完整代码见：

public static int[] hitBricks(int[][] grid, int[][] hits) {
        for (int[] hit : hits) {
            if (grid[hit[0]][hit[1]] == 1) {
                grid[hit[0]][hit[1]] = 2;
            }
        }
        UnionFind unionFind = new UnionFind(grid);
        int[] ans = new int[hits.length];
        for (int i = hits.length - 1; i >= 0; i--) {
            if (grid[hits[i][0]][hits[i][1]] == 2) {
                ans[i] = unionFind.finger(hits[i][0], hits[i][1]);
            }
        }
        return ans;
    }

    // 并查集
    public static class UnionFind {
        private int row;
        private int col;
        // 连在天花板上的集合的元素个数
        private int cellingAll;
        // 原始矩阵
        private int[][] grid;
        // 是否连在天花板上
        private boolean[] cellingSet;
        private int[] parents;
        private int[] size;
        private int[] help;

        public UnionFind(int[][] matrix) {
            grid = matrix;
            row = grid.length;
            col = grid[0].length;
            int all = row * col;
            cellingAll = 0;
            cellingSet = new boolean[all];
            parents = new int[all];
            size = new int[all];
            help = new int[all];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == 1) {
                        int index = i * col + j;
                        parents[index] = index;
                        size[index] = 1;
                        if (i == 0) {
                            cellingSet[index] = true;
                            cellingAll++;
                        }
                    }
                }
            }
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == 1) {
                        union(i, j, i - 1, j);
                        union(i, j, i + 1, j);
                        union(i, j, i, j - 1);
                        union(i, j, i, j + 1);
                    }
                }
            }
        }

        private int index(int i, int j) {
            return i * col + j;
        }

        private int find(int i) {
            int hi = 0;
            while (i != parents[i]) {
                help[hi++] = i;
                i = parents[i];
            }
            for (int j = 0; j < hi; j++) {
                parents[help[j]] = i;
            }
            return i;
        }

        private void union(int r1, int c1, int r2, int c2) {
            if (valid(r1, c1) && valid(r2, c2)) {
                int father1 = find(index(r1, c1));
                int father2 = find(index(r2, c2));
                if (father1 != father2) {
                    int size1 = size[father1];
                    int size2 = size[father2];
                    boolean status1 = cellingSet[father1];
                    boolean status2 = cellingSet[father2];
                    if (size1 <= size2) {
                        parents[father1] = father2;
                        size[father2] = size1 + size2;
                        if (status1 ^ status2) {
                            cellingSet[father2] = true;
                            cellingAll += status1 ? size2 : size1;
                        }
                    } else {
                        parents[father2] = father1;
                        size[father1] = size1 + size2;
                        if (status1 ^ status2) {
                            cellingSet[father1] = true;
                            cellingAll += status1 ? size2 : size1;
                        }
                    }
                }
            }
        }

        private boolean valid(int row, int col) {
            return row >= 0 && row < this.row && col >= 0 && col < this.col;
        }

        public int finger(int i, int j) {
            grid[i][j] = 1;
            int cur = i * col + j;
            if (i == 0) {
                cellingSet[cur] = true;
                cellingAll++;
            }
            parents[cur] = cur;
            size[cur] = 1;
            int pre = cellingAll;
            union(i, j, i - 1, j);
            union(i, j, i + 1, j);
            union(i, j, i, j - 1);
            union(i, j, i, j + 1);
            int now = cellingAll;
            if (i == 0) {
                return now - pre;
            } else {
                return now == pre ? 0 : now - pre - 1;
            }
        }
    }

更多

算法和数据结构笔记