Given a boolean 2D matrix,0is represented as the sea,1is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Find the number of islands.

Have you met this question in a real interview?

Yes

Example

Given graph:

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

return3.

1可以用dfs, bfs来做， 但无法解决动态问题， 所以用union find 的衍生，查询所有集合的数量，初始集合数量时注意不是全部的点，而是所有的岛屿

class UnionFind {
    int[] father = null;
    int count;
    public UnionFind(int n) {
        father = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            father[i] = i;
        }
    }

    private int find(int a) {
        if (father[a] == a) {
            return a;
        }

        return father[a] = find(father[a]);
    }

    public boolean isConnected(int a, int b) {
        return find(a) == find(b);
    }

    public void connect(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);

        if (root_a != root_b) {
            father[root_a] = root_b;
            count--;
        }
    }

    public int query() {
        return count;
    }

    public void setCount(int a) {
        count = a;
    }
}
public class Solution {
    /*
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */

    public int numIslands(boolean[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }

        UnionFind uf = new UnionFind(grid.length * grid[0].length);
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j]) {
                    count++;
                }
            }
        }

        uf.setCount(count);

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j]) {
                    if (i - 1 >= 0 && grid[i - 1][j]) {
                        uf.connect(i * grid[i].length + j, (i - 1) * grid[i].length + j);
                    }

                    if (i + 1 < grid.length && grid[i + 1][j]) {
                        uf.connect(i * grid[i].length + j, (i + 1) * grid[i].length + j);
                    }

                    if (j + 1 < grid[i].length && grid[i][j + 1]) {
                        uf.connect(i * grid[i].length + j, i * grid[i].length + (j + 1));
                    }

                    if (j - 1 >= 0 && grid[i][j - 1]) {
                        uf.connect(i * grid[i].length + j, i * grid[i].length + (j - 1));
                    }
                }
            }
        }
        return uf.query();
    }
}