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
Given n = 3, m = 3, array of pair A = [(0,0),(0,1),(2,2),(2,1)].

return [1,1,2,2].

Union Find

lintcode 433 Number of Islands 这个题目除了Union Find，还可以用DFS或BFS做。但是对于这个follow up，就最好用Union Find来解决了.

这种题目主要是需要把二维数组一维化:

  1. nums[i][j] i ∈ [0, n), j ∈ [0, m)
  2. 对于 i, j, 相对应的一维数组中的数为 i * m + j;
  3. 对于 k ∈ [0, m * n), 相对应的二维数组中的数为nums[k / m][k % m].
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
50
public class Solution {
    
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        HashMap<Integer, Integer> fathers = new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        int count = 0;
        if (operators == null)
            return ans;
        for (Point p : operators) {
            count++;
            int idx = twod2oned(p.x, p.y, n, m);
            fathers.put(idx, idx);
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;
                int neighbor = twod2oned(nx, ny, n, m);
                if (fathers.containsKey(neighbor)) {
                    int neighborGroup = find(fathers, neighbor);
                    if (neighborGroup != idx) {
                        fathers.put(neighborGroup, idx);
                        count--;
                    }
                }
            }
            ans.add(count);
        }
        return ans;
    }
    private int find(HashMap<Integer, Integer> fathers, int x) {
        int fa = fathers.get(x);
        while (fa != fathers.get(fa)) {
            fa = fathers.get(fa);
        }
        return fa;
    }
    private int twod2oned(int i, int j, int n, int m) {
        return i * m + j;
    }
}