Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.

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

Example

Givenn=3,m=3, array of pair A =[(0,0),(0,1),(2,2),(2,1)].

return[1,1,2,2].

Solution:

union find: 检查与上下左右的点是否在同一个集合，如果不是，union, count--

dfs: 每碰到一个1，就把周围四个变为0，最后剩下的1个数即岛数

    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        List<Integer> ans = new ArrayList<Integer>();

        if(operators == null || operators.length == 0){
            return ans;
        }

        UnionFind uf = new UnionFind(n, m);
        int[][] island = new int[n][m];
        int count = 0;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        for(int i = 0; i < operators.length; i++){
            int x = operators[i].x;
            int y = operators[i].y;
            int id1 = convert(x, y, m);
            island[x][y] = 1;
            count++;
            for(int j = 0; j < 4; j++){
                int x2 = x + dx[j];
                int y2 = y + dy[j];
                if(x2 < n && x2 >= 0 && y2 >= 0 && y2 < m && island[x2][y2] == 1){
                    int id2 = convert(x2, y2, m);
                    if(uf.compressed_find(id1) != uf.compressed_find(id2)){
                        count--;
                        uf.union(id1, id2);
                    }
                }
            }
            ans.add(count);
        }

        return ans;
    }

    public int convert(int x, int y, int n){
            return x * n + y;
    }

    class UnionFind{
            HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

            public UnionFind(int m, int n){
                for(int i = 0; i < m; i++){
                    for(int j = 0; j < n; j++){
                        int id = convert(i, j, n);
                        father.put(id, id);
                    }
                }
            }

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

            public void union(int x, int y){
                int fa_x = compressed_find(x);
                int fa_y = compressed_find(y);
                if(fa_x != fa_y){
                    father.put(fa_x, fa_y);
                }
            }
    }