union-find 算法

1、前言

union-find 为并查集算法，原本的用途是判断图的连通性问题，连通性是指图中的两个节点是否相连。说到这，我们是否能想到用 dfs、bfs 判断连通性问题？其实是可以的，union-find 只是多出来一种解决思路而已。

所以记住一点，基本上能用并查集来做的题，bfs、dfs 都能做。

2、概念

并查集的概念很简单，就是原本大家都是在不同的集合里，然后通过合并，最后合并到一个集合里面，就像不同的帮派合并一样。并查集最基本的功能就是 union（合并）。代码如下：

public class UnionFind {
        private int[] parent;

        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        private int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot == yRoot) {
                return;
            }

            parent[xRoot] = yRoot;
        }
    }

我们可以用并查集来做一个岛问题。岛问题用 dfs、bfs 都很好找，并查集也很好做。核心思想：将都是1的地方用并查集合并起来，然后最后并查集中1的数量就是岛屿的数量。

class Solution {
    public int numIslands(char[][] grid){
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }

        int[][] directions = {{1, 0}, {0, 1}};
        int row = grid.length, column = grid[0].length, space = 0;
        UnionFind unionFind = new UnionFind(row * column);
        for(int i = 0; i < row; i++){
            for(int j = 0; j < column; j++){
                if(grid[i][j] == '0'){
                    space++;
                }else {
                    for (int[] direction : directions) {
                        int newX = i + direction[0];
                        int newY = j + direction[1];
                        if(newX < row && newY < column && grid[newX][newY] == '1'){
                            unionFind.union(i * column + j, newX * column + newY);
                        }
                    }
                }
            }
        }

        return unionFind.count - space;
    }

    class UnionFind{
        private int[] parent;
        private int count;

        public UnionFind(int n){
            this.count = n;
            this.parent = new int[n];
            for(int i = 0; i < n; i++){
                this.parent[i] = i;
            }
        }

        private int find(int x){
            while(x != this.parent[x]){
                this.parent[x] = this.parent[this.parent[x]];
                x = this.parent[x];
            }
            return x;
        }

        public void union(int x, int y){
            int xParent = find(x);
            int yParent = find(y);
            if(xParent == yParent){
                return;
            }
            this.parent[xParent] = yParent;
            this.count--;
        }
    }
}