200. 岛屿数量

floodfill算法：https://blog.csdn.net/qq_40794973/article/details/102473737

并查集 Union Find：https://blog.csdn.net/qq_40794973/article/details/102944107 

 https://leetcode-cn.com/problems/number-of-islands/

---

并查集 Union Find

• m = 3 //行
• n = 4 //列

(0, 0)	(0, 1)	(0, 2)	(0, 3)
(1, 0)	(1, 1)	(1, 2)	(1, 3)
(2, 0)	(2, 1)	(2, 2)	(2, 3)

 i * n + j //n列数(4)

0	1	2	3
4	5	6	7
8	9	10	11

先假设所有的陆地都是一个独立的岛屿，后面在合并即可

class Solution {
    class UnionFind {
        int count; //岛屿数量
        int[] parent;
        int[] rank;
        public UnionFind(char[][] grid) {
            count = 0;
            //行
            int m = grid.length;
            //列
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    //陆地
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        //假设每个陆地都是一个岛屿
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }
        // 查找过程, 查找元素p所对应的集合编号
        // O(h)复杂度, h为树的高度
        public int find(int p) {
            // 不断去查询自己的父亲节点, 直到到达根节点
            // 根节点的特点: parent[p] == p
            if (parent[p] != p) {
                parent[p] = find(parent[p]);
            }
            return parent[p];
        }
        // 合并元素p和元素q所属的集合
        // O(h)复杂度, h为树的高度
        public void unionElements(int p, int q) {
            int rootx = find(p);
            int rooty = find(q);
            if (rootx != rooty) {
                // 根据两个元素所在树的层数不同判断合并方向
                // 将层数少的集合合并到层数多的集合上
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {// rank[rootx] == rank[rooty]
                    parent[rooty] = rootx;
                    // 此时才维护rank的值
                    rank[rootx] += 1;
                }
                //两个岛屿合并成一个了，岛屿数量减一
                --count;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        //行
        int m = grid.length;
        //列
        int n = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                //如果是陆地尝试在四个方向上进行合并
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    //下
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                        uf.unionElements(i * n + j, (i - 1) * n + j);
                    }
                    //上
                    if (i + 1 < m && grid[i + 1][j] == '1') {
                        uf.unionElements(i * n + j, (i + 1) * n + j);
                    }
                    //左
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                        uf.unionElements(i * n + j, i * n + j - 1);
                    }
                    //右
                    if (j + 1 < n && grid[i][j + 1] == '1') {
                        uf.unionElements(i * n + j, i * n + j + 1);
                    }
                }
            }
        }
        return uf.getCount();
    }
}