Number of Islands II

You are given an empty m x n grid initially filled with water. We may perform an addLand operation where positions[i] = [ri, ci] turns the cell (ri, ci) into land. Return an array answer where answer[i] is the number of islands after the ith operation. An island is a maximal group of horizontally or vertically adjacent land cells.

Example 1:

` Input: m = 3, n = 3, positions = [[1,1], [2,1], [2,2], [1,2], [3,3], [3,2], [1,3], [2,3], [2,4]] Output: [1,2,2,3,3,3,4,5,6] Explanation:

1. Initially, we have 0 islands.
2. After adding land at (1, 1), we have 1 island.
3. Adding land at (2, 1) connects the existing island, so we still have 1 island.
4. Adding land at (2, 2) connects the existing island, so we still have 1 island.
5. Adding land at (1, 2) connects the existing island, so we still have 1 island.
6. Adding land at (3, 3) creates a new island, so we now have 2 islands.
7. Adding land at (3, 2) connects the existing island, so we still have 2 islands.
8. Adding land at (1, 3) connects the existing island, so we still have 2 islands.
9. Adding land at (2, 3) connects the existing island, so we still have 2 islands.
10. Adding land at (2, 4) creates a new island, so we now have 3 islands. `

Example 2:

Input: m = 1, n = 1, positions = [[1,1]] Output: [1]

Constraints:

• 1 <= m, n <= 50
• 1 <= positions.length <= 50
• positions[i].length == 2
• 1 <= ri <= m
• 1 <= ci <= n

Hint:

• You can use the Union-Find data structure to solve this problem.