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

作者: Grey

原文地址：使用并查集解决的相关问题

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

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

相关题目#

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

待更新....

更多#

算法和数据结构笔记