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