Question: 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:

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

Union Find

Below: standard UF; no union by rank or path compression; understand UF totally first!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    int[][] dirs = {{0,1}, {0, -1}, {1, 0}, {-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[] map = new int[m * n];
        Arrays.fill(map, -1);
        
        for (int[] p : positions) {
            int root = n * p[0] + p[1];
            
            if (map[root] != -1) { 
                res.add(count); 
                continue; 
            }
            
            map[root] = root; // UF初始化, 所有节点的父节点都赋值为自己; new island
            count++; // add a new island
            
            for (int[] d : dirs) {
                int x = p[0] + d[0];
                int y = p[1] + d[1];
                int idNb = n * x + y;
                if (x < 0 || x >= m || y < 0 || y >= n || map[idNb] == -1) continue;
                
                int rootNb = findIsland(map, idNb);
                root = findIsland(map, root); // 找到当前节点的root
                // 上面的两行，直接找到最顶端的root而不仅仅是parent
                
                if (root != rootNb) {
                    map[root] = rootNb; // 当前节点的root赋值为rootNb, ie. union
                    count--;
                }
            }
            
            res.add(count);
        }
        
        return res;
    }
    
    public int findIsland(int[] map, int id) {
        while (id != map[id]) id = map[id];
        return id;
    }
}