提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
并查集（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;
}
}
}
