力扣labuladong——一刷day80

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

并查集（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;
        }
    }
}