Number of Islands II

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.

Notice

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].

class UnionFind {
    int[] arr;
    public UnionFind(int n) {
        arr = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            arr[i] = i;
        }
    }
    public void union(int n1, int n2) {
        int p1 = find(n1);
        int p2 = find(n2);
        if(p1 != p2) {
            arr[p1] = arr[p2];
        }
    }
    public int find(int n) {
        if(n != arr[n]) {
            int father = find(arr[n]);
            return father;
        }
        return n;
    }
}
public List<Integer> numIslands2(int n, int m, Point[] operators) {
    List<Integer> res = new ArrayList<Integer>();
    if(operators == null || operators.length == 0) {
        return res;
    }
    int[] dx = new int[]{1, 0, -1, 0};
    int[] dy = new int[]{0, 1, 0, -1}
    UnionFind uf = new UnionFind(n * m);
    boolean[][] hash = new boolean[n][m];
    int count = 0;
    for(Point p : operators) {
        int index = p.x * m + p.y;
        hash[p.x][p.y] = true;
        count++;
        for(int j = 0; j < 4; j++) {
            int nx = p.x + dx[j];
            int ny = p.y + dy[j];
            int nindex = nx * m + ny;
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && hash[nx][ny]) {
                if(uf.find(index) != uf.find(nindex)) {
                    uf.union(nindex, index);
                    count--;
                }
            }
        }
        res.add(count);
    }
    return res;
}