力扣labuladong一刷day46天并查集

力扣labuladong一刷day46天并查集

一、323. 无向图中连通分量的数目

题目链接：https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/description/
思路：求联通分量一般是通过并查集，而构建并查集则非常简单，使用一个数组模拟森林，每个槽位记录对应的父节点，合并两个集合时只需要把一个根节点作为另一个根节点的子节点，此外为了提升效率，在查询根节点的过程中可以采用压缩路径的方法，即不断的让当前节点与其父节点做兄弟。

class Solution {
    public int countComponents(int n, int[][] edges) {
        UF uf = new UF(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.count;
    }

    class UF {
        int[] parent;
        int count;
        public UF(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            count = n;
        }

        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        boolean connected(int x, int y) {
            return find(x) == find(y);
        }

        void union(int x, int y) {
            int p = find(x);
            int q = find(y);
            if (p == q) return;
            parent[p] = q;
            count--;
        }
    }
}

二、130. 被围绕的区域

题目链接：https://leetcode.cn/problems/surrounded-regions/
思路：这是一个岛屿问题，也是棋盘问题，其实描述的是一件事情。一般采用dfs解决。本题要求与边界不相邻的修改为X，与边界相邻的不动。其实我们可以只dfs与边界相邻的，修改为A。之后直接for循环遍历棋盘，把O改为X，把A改为O。

class Solution {
      public void solve(char[][] board) {
        int row = board.length, col = board[0].length;
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][col-1] == 'O') dfs(board, i, col-1);
        }
        for (int i = 0; i < col; i++) {
            if (board[0][i] == 'O') dfs(board, 0, i);
            if (board[row-1][i] == 'O') dfs(board, row-1, i);
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'A') board[i][j] = 'O';
            }
        }
    }

    void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || 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);
    }
}

三、990. 等式方程的可满足性

题目链接：https://leetcode.cn/problems/satisfiability-of-equality-equations/
思路：把相等的进行连接，然后逐个判断不等的看看是否在一个联通里，如果不等的在一个联通里即不满住可满足性。

class Solution {
   public boolean equationsPossible(String[] equations) {
        UF uf = new UF(26);
        for (String s : equations) {
            if (s.charAt(1) == '=') {
                uf.union(s.charAt(0)-'a', s.charAt(3)-'a');
            }
        }
        for (String s : equations) {
            if (s.charAt(1) == '!') {
                if (uf.connected(s.charAt(0)-'a', s.charAt(3)-'a')) {
                    return false;
                }
            }
        }
        return true;
    }

    class UF {
        int[] parent;
        int count;
        public UF(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            count = n;
        }
        int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        boolean connected(int x, int y) {
            return find(x) == find(y);
        }

        void union(int x, int y) {
            int a = find(x);
            int b = find(y);
            if (a == b)return;
            parent[a] = b;
            count--;
        }
    }
}