算法笔记-查并集类

具体详解

https://mikeygithub.github.io/2021/01/08/yuque/chgv64/

相关题目

200. 岛屿数量（mid）

class Solution {

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        UnionFind uf = new UnionFind(grid);
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';
                    if (r - 1 >= 0 && grid[r-1][c] == '1') {
                        uf.union(r * nc + c, (r-1) * nc + c);
                    }
                    if (r + 1 < nr && grid[r+1][c] == '1') {
                        uf.union(r * nc + c, (r+1) * nc + c);
                    }
                    if (c - 1 >= 0 && grid[r][c-1] == '1') {
                        uf.union(r * nc + c, r * nc + c - 1);
                    }
                    if (c + 1 < nc && grid[r][c+1] == '1') {
                        uf.union(r * nc + c, r * nc + c + 1);
                    }
                }
            }
        }
        return uf.getCount();
    }
    //并查集
    class UnionFind {
        int count;
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }

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

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

        public int getCount() {
            return count;
        }
    }
}

6106. 统计无向图中无法互相到达点对数（mid）

1697. 检查边长度限制的路径是否存在（hard）

class Solution {
    //并查集
    //1.把小于limit的edge加入并查集
    //2.排序后，一边判断一边加入并查集

    //edgeList[i] = [ui, vi, disi]
    //queries[j] = [pj, qj, limitj]
   public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        int m = queries.length;
        int k = edgeList.length;
        boolean[] ret = new boolean[m];
         Arrays.sort(edgeList, Comparator.comparingInt(a -> a[2]));
         Integer[] sit = new Integer[m];
         for(int i=0;i<m;i++)sit[i] = i;
         Arrays.sort(sit, Comparator.comparingInt(a -> queries[a][2]));
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int idx = 0;
        for (int i:sit) {
            int[] query = queries[i];
            while (idx<k&&edgeList[idx][2]<query[2]){
                union(edgeList[idx][0],edgeList[idx][1]);
                idx++;
            }
            ret[i] = find(query[0]) == find(query[1]);
        }
        return ret;
    }

    int[] parent;

    public int find(int i) {
        // 如果 i 是自己的父节点（代表）
        if (parent[i] == i) {
            return i;
        } else {
            //如果当前parent不是代表继续沿着树向上移动，直到找到代表
            return find(parent[i]);
        }
    }

    //将包含i的集合统一起来,还有包括j
    void union(int i, int j) {
        //查找包含i的集合的代表（或根节点）
        int irep = find(i);
        //对包含j的集合也要这样做
        int jrep = find(j);
        //使i的代表的父节点成为j的代表（有效地将所有i的集合移动到j的集合中）
        parent[irep] = jrep;
    }
}

相关资料