305. Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

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

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

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

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

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

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

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

We return the result as an array: [1, 1, 2, 3]

Challenge:
Can you do it in time complexity O(k log mn), where k is the length of the positions?

一刷
题解：原先的思路是，如果加进去的自成一个岛屿，count++, 如果和别的连在了一块，count不变。但是其实加进去的可能把多个岛屿连成了一片。
算法：union-find
对于union-find来说，相当于构造了一个树的结构，不停地调用

while(id!=roots[id]){
            roots[id] = roots[roots[id]];
            id = roots[id];
        }

最后会返回根节点的index, 如果两个不同的点找到了同一个根，那么这两个点连成一片

class Solution {
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList<>();
        if(m<=0 || n<=0) return res;
        int count = 0;
        int[] roots = new int[m*n]; //one island = one set
        Arrays.fill(roots, -1);
        for(int[] p : positions){
            int root = n*p[0] + p[1]; //assume new point is isolated island
            roots[root] = root;
            count++;
            
            for(int[] dir : dirs){
                int x = p[0] + dir[0];
                int y = p[1] + dir[1];
                int nb = n * x + y;
                if(x < 0 || x >= m || y < 0 || y >= n || roots[nb] == -1) continue;
                int rootNb = findIsLand(roots, nb);
                //int rootNb = roots[nb];
                if(root!=rootNb){
                    roots[root] = rootNb;//change the current island to adjacent land index
                    root = rootNb;
                    count--; //current root = joined tree root
                }
            }
            res.add(count);
        }
        return res;
    }
    
    private int findIsLand(int[] roots, int id){
        while(id!=roots[id]){
            roots[id] = roots[roots[id]];
            id = roots[id];
        }
        return id;
    }
}