Number of Islands

Number of Islands I，遍历整个grid，每遇到一个character等于'1'，往右和往下看一下，如果也是‘1’,就union一下。

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

        UnionFind uf = new UnionFind(grid);
        int m = grid.length, n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '1') {
                    continue;
                }

                int index1 = i * n + j;
                if (i + 1 < m && grid[i + 1][j] == '1') {
                    int index2 = (i + 1) * n + j;
                    uf.union(index1, index2);
                }
                if (j + 1 < n && grid[i][j + 1] == '1') {
                    int index2 = i * n + j + 1;
                    uf.union(index1, index2);
                }
            }
        }

        return uf.numOfComponent;
    }
}

class UnionFind {
    Map<Integer, Integer> parent = new HashMap<Integer, Integer>();
    Map<Integer, Integer> size = new HashMap<Integer, Integer>();
    int numOfComponent;

    public UnionFind(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    int index = i * n + j;
                    parent.put(index, index);
                    size.put(index, 1);
                    numOfComponent++;
                }
            }
        }
    }

    public int find(int x) {
        int father = parent.get(x);
        while (father != parent.get(father)) {
            father = parent.get(father);
        }

        while (parent.get(x) != father) {
            int next = parent.get(x);
            parent.put(x, father);
            x = next;
        }

        return father;
    }

    public void union(int x, int y) {
        int x_father = find(x);
        int y_father = find(y);

        if (x_father != y_father) {
            int x_size = size.get(x_father);
            int y_size = size.get(y_father);

            if (x_size > y_size) {
                parent.put(y_father, x_father);
                size.put(x_father, x_size + y_size);
            } else {
                parent.put(x_father, y_father);
                size.put(y_father, x_size + y_size);
            }
            numOfComponent--;
        }
    }
}

Number of Islands II， online algorithm，每次新加入一个点，就add这个点进uf.parent_map，并且numOfComponent加一。同时往上下左右看一下，如果能union，就union并且numOfComponent减一。

public class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        UnionFind uf = new UnionFind();
        final int[] dx = {0, 0, -1, 1};
        final int[] dy = {-1, 1, 0, 0};

        List<Integer> result = new ArrayList<Integer>();
        for (int[] p: positions) {
            int i = p[0], j = p[1];
            int index = i * n + j;
            uf.add(index);

            for (int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    int index2 = x * n + y;
                    if (uf.parent.containsKey(index2)) {
                        uf.union(index, index2);                        
                    }
                }
            }
            result.add(uf.numOfComponent);
        }

        return result;
    }
}

class UnionFind {
    Map<Integer, Integer> parent = new HashMap<Integer, Integer>();
    Map<Integer, Integer> size = new HashMap<Integer, Integer>();
    int numOfComponent;

    public void add(int index) {
        parent.put(index, index);
        size.put(index, 1);
        numOfComponent++;
    }

    public int find(int x) {
        int father = parent.get(x);

        while (father != parent.get(father)) {
            father = parent.get(father);
        }

        while (parent.get(x) != father) {
            int next = parent.get(x);
            parent.put(x, father);
            x = next;
        }

        return father;
    }

    public void union(int x, int y) {
        int x_father = find(x);
        int y_father = find(y);

        if (x_father != y_father) {
            int x_size = size.get(x_father);
            int y_size = size.get(y_father);

            if (x_size > y_size) {
                parent.put(y_father, x_father);
                size.put(x_father, x_size + y_size);
            } else {
                parent.put(x_father, y_father);
                size.put(y_father, x_size + y_size);
            }
            numOfComponent--;
        }
    }
}