珠海市网站设计公司,石英石台面做网单有什么网站,素材天下,简易的网站模板力扣labuladong一刷day46天并查集 文章目录 力扣labuladong一刷day46天并查集一、323. 无向图中连通分量的数目二、130. 被围绕的区域三、990. 等式方程的可满足性 一、323. 无向图中连通分量的数目
题目链接#xff1a;https://leetcode.cn/problems/number-of-connected-co…力扣labuladong一刷day46天并查集 文章目录 力扣labuladong一刷day46天并查集一、323. 无向图中连通分量的数目二、130. 被围绕的区域三、990. 等式方程的可满足性 一、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, x1, y);dfs(board, x, y-1);dfs(board, x, y1);}
}三、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--;}}
}
