305 Number of Islands II

給一個m*n的matrix，初始值都是0，0表示是海，1表示是土地。給int[][] position，表示要加入土地的位置，addLand() 會根據給的position一一加入土地。問每一步addLand之後，matrix上會有多少個島。

Example

Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]

第一次 addLand(0,0)

1 0 0
0 0 0   Number of islands = 1
0 0 0

第二次 addLand(0,1)

1 1 0
0 0 0   Number of islands = 1
0 0 0

第三次addLand(1,2)

1 1 0
0 0 1   Number of islands = 2
0 0 0

第四次addLane(2,1)

1 1 0
0 0 1   Number of islands = 3
0 1 0

Idea 這是一題標準的Union Find題目。每一個島即是a set of 1s。 每當新加入一個position屬於某set，或導致某set和另個set變成同個set，就要Union 當需要知道某兩個位置是否屬於同個set，就要進行Find，來看兩者的parent是否相同。

Pseudocode

Create an ArrayList for saving # of island after each addLand operation
Create an int count to record current # of island
Each position on matrix have an id: n * x + y
Create a UnionFindSet

Each time add a position
    Set it's parent to itself
    count++
    check all four neighbors
        if neighbors is in the boundary
            Find(neighbor)
            if neighbor's parent is not -1
                Union 2 islands by rank
                count--
    result.add(count)

return result

Code

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        UnionFindSet set = new UnionFindSet(m*n);
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        List<Integer> result = new ArrayList<>();
        int count = 0;

        for(int[] p : positions){
            int idx = p[0]*n + p[1];
            count++;
            set.setParent(idx);//nx+y
            //check if four neighbors has 1
            for(int[] d : dirs){
                int nx = d[0] + p[0];
                int ny = d[1] + p[1];
                if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int ni = n * nx + ny;//neighbor index
                if(set.Find(ni) != -1){
                    if(set.Union(idx, ni)){
                        count--;
                    }
                }
            }
            result.add(count);
        }

        return result;
    }
}

class UnionFindSet {
    private int[] parents;
    private int[] ranks;

    public UnionFindSet(int n) {
        parents = new int[n+1];
        ranks = new int[n+1];
        for(int i=0; i< parents.length; i++){
            parents[i] = -1;
            ranks[i] = 0;
        }
    }

    public void setParent(int u){
        parents[u] = u;
    }

    public boolean Union(int u, int v) {
        int pu = Find(u);
        int pv = Find(v);
        if(pu == pv)    return false;//no need to union, already in the same cluster
        if(ranks[pv] > ranks[pu])
            parents[pu] = pv;
        else if(ranks[pu] < ranks[pv])
            parents[pv] = pu;
        else{
            parents[pv] = pu;
            ranks[pu] += 1;
        }

        return true;
    }

    public int Find(int u){
        if(parents[u] == -1)    return -1;
        while(parents[u] != u){
            parents[u] = parents[parents[u]];
            u = parents[u];
        }
        return u;
    }
}