434. 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.
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.
Given n = 3, m = 3, array of pair A = [(0,0),(0,1),(2,2),(2,1)].
lintcode 433 Number of Islands 这个题目除了Union Find，还可以用DFS或BFS做。但是对于这个follow up，就最好用Union Find来解决了.
- nums[i][j] i ∈ [0, n), j ∈ [0, m)
- 对于 i, j, 相对应的一维数组中的数为 i * m + j;
- 对于 k ∈ [0, m * n), 相对应的二维数组中的数为nums[k / m][k % m].