力扣labuladong——一刷day80
2023-12-28 22:29:50
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
并查集(Union-Find)算法是一个专门针对「动态连通性」的算法,我之前写过两次,因为这个算法的考察频率高,而且它也是最小生成树算法的前置知识,所以我整合了本文,争取一篇文章把这个算法讲明白。
一、力扣323.无向图中连通分量的数目
class UF{
private int[]parent;
private int count;
public UF(int n){
parent = new int[n];
count = n;
for(int i = 0; i < n; i ++){
parent[i] = i;
}
}
public int getCount(){
return count;
}
public int find(int x){
while(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y){
int rootX = find(x);
int rootY = find[y];
if(rootX == rooY){
return;
}
parent[rootX] = rootY;
count --;
}
public boolean getConnection(int x, int y){
int rootX = find(x);
int rootY = find(y);
return rootX == rootY;
}
public int fun(int n, int[][] edges){
UF uf = new UF(n);
for(int i = 0; i < n; i ++){
union(edges[i][0], edges[i][1]);
}
return getCount();
}
}
二、力扣130. 被围绕的区域
class Solution {
public void solve(char[][] board) {
int[][] arr = new int[][]{
{0,1},
{0,-1},
{-1,0},
{1,0}
};
if(board == null || board.length == 0){
return;
}
int m = board.length;
int n = board[0].length;
int dummy = m * n;
UF uf = new UF(dummy+1);
for(int i = 0; i < m; i ++){
if(board[i][0] == 'O'){
uf.union(i*n,dummy);
}
if(board[i][n-1] == 'O'){
uf.union(i*n+n-1,dummy);
}
}
for(int i = 0; i < n; i ++){
if(board[0][i] == 'O'){
uf.union(i,dummy);
}
if(board[m-1][i] == 'O'){
uf.union((m-1)*n+i,dummy);
}
}
for(int i = 1; i < m-1; i ++){
for(int j = 1; j < n-1; j ++){
if(board[i][j] == 'O'){
for(int k = 0; k < 4; k ++){
int X = i + arr[k][0];
int Y = j + arr[k][1];
if(board[X][Y] == 'O'){
uf.union(X*n+Y,i*n+j);
}
}
}
}
}
for(int i = 0; i < m; i ++){
for(int j = 0; j < n; j ++){
if(board[i][j] == 'O' && !uf.getConnection(i*n+j, dummy)){
board[i][j] = 'X';
}
}
}
}
class UF{
private int count;
private int[] parent;
public UF(int n){
count = n;
parent = new int[n];
for(int i = 0; i < n; i ++){
parent[i] = i;
}
}
public int getCount(){
return count;
}
public int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY){
return;
}
parent[rootX] = rootY;
count --;
}
public boolean getConnection(int x, int y){
int rootX = find(x);
int rootY = find(y);
return rootX == rootY;
}
}
}
文章来源:https://blog.csdn.net/ResNet156/article/details/135272493
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!