面试算法大全-并查集总结

太过爱你忘了你带给我的痛 2022-10-06 13:57 72阅读 0赞

## 14 、并查集 ##

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

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

### 14.1 并查集总结 ###

并查集的实现

public class QuickUnionUF {
        
        //存储若干棵树
        private int[] parent;
        //记录连通分量
        private int count;
    
        /**
         * 初始化 parent等于它自己
         * @param N 图的节点总数
         */
        public QuickUnionUF(int N){
        
            this.count=N;
            parent=new int[N];
            for (int i = 0; i < N; i++) {
        
                parent[i]=i;
            }
        }
        public int findRoot(int i){
        
            int root=i;
            while (root != parent[root]) {
        
                root=parent[root];
            }
            //路径压缩
            while (i!=parent[i]){
        
                int tmp=parent[i];
                parent[i]=root;
                i=tmp;
            }
            return root;
        }
        /**
         * 返回某个节点x的根节点
         * @param x
         * @return
         */
        public int find(int x){
        
            while (parent[x]!=x){
        
                x=parent[x];
            }
            return x;
        }
        /**
         *判断是否有相同的根节点
         */
        public boolean connected(int p,int q){
        
            return findRoot(p)==findRoot(q);
        }
        /**
         * 合并
         * @param p
         * @param q
         */
        public void union(int p,int q){
        
            int qroot=findRoot(q);
            int proot=findRoot(p);
            if (qroot==proot) {
        
                return;
            }
            parent[proot]=qroot;
            //
            //parent[qroot]=proot;也是一样的
            count--;
        }
        /**
         * 返回当前的连通分量个数
         * @return
         */
        public int count(){
        
            return count;
        }

### 14.2 经典题目源码总结 ###

#### [朋友圈][Link 1] ####

方法 1：深度优先搜索

public class Solution {
        
        public void dfs(int[][] M, int[] visited, int i) {
        
            for (int j = 0; j < M.length; j++) {
        
                if (M[i][j] == 1 && visited[j] == 0) {
        
                    visited[j] = 1;
                    dfs(M, visited, j);
                }
            }
        }
        public int findCircleNum(int[][] M) {
        
            int[] visited = new int[M.length];
            int count = 0;
            for (int i = 0; i < M.length; i++) {
        
                if (visited[i] == 0) {
        
                    dfs(M, visited, i);
                    count++;
                }
            }
            return count;
        }
    }

方法 2：广度优先搜索

public class Solution {
        
        public int findCircleNum(int[][] M) {
        
            int[] visited = new int[M.length];
            int count = 0;
            Queue < Integer > queue = new LinkedList < > ();
            for (int i = 0; i < M.length; i++) {
        
                if (visited[i] == 0) {
        
                    queue.add(i);
                    while (!queue.isEmpty()) {
        
                        int s = queue.remove();
                        visited[s] = 1;
                        for (int j = 0; j < M.length; j++) {
        
                            if (M[s][j] == 1 && visited[j] == 0)
                                queue.add(j);
                        }
                    }
                    count++;
                }
            }
            return count;
        }
    }

方法 3：并查集

public class Solution {
        
        int find(int parent[], int i) {
        
            if (parent[i] == -1)
                return i;
            return find(parent, parent[i]);
        }
    
        void union(int parent[], int x, int y) {
        
            int xset = find(parent, x);
            int yset = find(parent, y);
            if (xset != yset)
                parent[xset] = yset;
        }
        public int findCircleNum(int[][] M) {
        
            int[] parent = new int[M.length];
            Arrays.fill(parent, -1);
            for (int i = 0; i < M.length; i++) {
        
                for (int j = 0; j < M.length; j++) {
        
                    if (M[i][j] == 1 && i != j) {
        
                        union(parent, i, j);
                    }
                }
            }
            int count = 0;
            for (int i = 0; i < parent.length; i++) {
        
                if (parent[i] == -1)
                    count++;
            }
            return count;
        }
    }

#### [岛屿数量][Link 2] ####

方法一：深度优先搜索

class Solution {
        
        void dfs(char[][] grid, int r, int c) {
        
            int nr = grid.length;
            int nc = grid[0].length;
    
            if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
        
                return;
            }
    
            grid[r][c] = '0';
            dfs(grid, r - 1, c);
            dfs(grid, r + 1, c);
            dfs(grid, r, c - 1);
            dfs(grid, r, c + 1);
        }
    
        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;
            for (int r = 0; r < nr; ++r) {
        
                for (int c = 0; c < nc; ++c) {
        
                    if (grid[r][c] == '1') {
        
                        ++num_islands;
                        dfs(grid, r, c);
                    }
                }
            }
    
            return num_islands;
        }
    }

方法二：广度优先搜索

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;
    
            for (int r = 0; r < nr; ++r) {
        
                for (int c = 0; c < nc; ++c) {
        
                    if (grid[r][c] == '1') {
        
                        ++num_islands;
                        grid[r][c] = '0';
                        Queue<Integer> neighbors = new LinkedList<>();
                        neighbors.add(r * nc + c);
                        while (!neighbors.isEmpty()) {
        
                            int id = neighbors.remove();
                            int row = id / nc;
                            int col = id % nc;
                            if (row - 1 >= 0 && grid[row-1][col] == '1') {
        
                                neighbors.add((row-1) * nc + col);
                                grid[row-1][col] = '0';
                            }
                            if (row + 1 < nr && grid[row+1][col] == '1') {
        
                                neighbors.add((row+1) * nc + col);
                                grid[row+1][col] = '0';
                            }
                            if (col - 1 >= 0 && grid[row][col-1] == '1') {
        
                                neighbors.add(row * nc + col-1);
                                grid[row][col-1] = '0';
                            }
                            if (col + 1 < nc && grid[row][col+1] == '1') {
        
                                neighbors.add(row * nc + col+1);
                                grid[row][col+1] = '0';
                            }
                        }
                    }
                }
            }
    
            return num_islands;
        }
    }

方法三：并查集

class Solution {
        
        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;
            }
        }
    
        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();
        }
    }

#### [被围绕的区域][Link 3] ####

方法一：深度优先搜索

class Solution {
        
        int n, m;
    
        public void solve(char[][] board) {
        
            n = board.length;
            if (n == 0) {
        
                return;
            }
            m = board[0].length;
            for (int i = 0; i < n; i++) {
        
                dfs(board, i, 0);
                dfs(board, i, m - 1);
            }
            for (int i = 1; i < m - 1; i++) {
        
                dfs(board, 0, i);
                dfs(board, n - 1, i);
            }
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < m; j++) {
        
                    if (board[i][j] == 'A') {
        
                        board[i][j] = 'O';
                    } else if (board[i][j] == 'O') {
        
                        board[i][j] = 'X';
                    }
                }
            }
        }
    
        public void dfs(char[][] board, int x, int y) {
        
            if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
        
                return;
            }
            board[x][y] = 'A';
            dfs(board, x + 1, y);
            dfs(board, x - 1, y);
            dfs(board, x, y + 1);
            dfs(board, x, y - 1);
        }
    }

方法二：广度优先搜索

class Solution {
        
        int[] dx = {
        1, -1, 0, 0};
        int[] dy = {
        0, 0, 1, -1};
    
        public void solve(char[][] board) {
        
            int n = board.length;
            if (n == 0) {
        
                return;
            }
            int m = board[0].length;
            Queue<int[]> queue = new LinkedList<int[]>();
            for (int i = 0; i < n; i++) {
        
                if (board[i][0] == 'O') {
        
                    queue.offer(new int[]{
        i, 0});
                }
                if (board[i][m - 1] == 'O') {
        
                    queue.offer(new int[]{
        i, m - 1});
                }
            }
            for (int i = 1; i < m - 1; i++) {
        
                if (board[0][i] == 'O') {
        
                    queue.offer(new int[]{
        0, i});
                }
                if (board[n - 1][i] == 'O') {
        
                    queue.offer(new int[]{
        n - 1, i});
                }
            }
            while (!queue.isEmpty()) {
        
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];
                board[x][y] = 'A';
                for (int i = 0; i < 4; i++) {
        
                    int mx = x + dx[i], my = y + dy[i];
                    if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O') {
        
                        continue;
                    }
                    queue.offer(new int[]{
        mx, my});
                }
            }
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < m; j++) {
        
                    if (board[i][j] == 'A') {
        
                        board[i][j] = 'O';
                    } else if (board[i][j] == 'O') {
        
                        board[i][j] = 'X';
                    }
                }
            }
        }
    }

方法三：并查集

class UnionFind {
        
        int[] parents;
    
        public UnionFind(int totalNodes) {
        
            parents = new int[totalNodes];
            for (int i = 0; i < totalNodes; i++) {
        
                parents[i] = i;
            }
        }
    		// 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
        void union(int node1, int node2) {
        
            int root1 = find(node1);
            int root2 = find(node2);
            if (root1 != root2) {
        
                parents[root2] = root1;
            }
        }
    
        int find(int node) {
        
            while (parents[node] != node) {
        
                // 当前节点的父节点 指向父节点的父节点.
                // 保证一个连通区域最终的parents只有一个.
                parents[node] = parents[parents[node]];
                node = parents[node];
            }
    
            return node;
        }
    
        boolean isConnected(int node1, int node2) {
        
            return find(node1) == find(node2);
        }
    }

[Link 1]: https://leetcode-cn.com/problems/friend-circles/
[Link 2]: https://leetcode-cn.com/problems/number-of-islands/
[Link 3]: https://leetcode-cn.com/problems/surrounded-regions/