You are given an empty m x n grid and a sequence of land additions. After each addition, return the number of islands. DSU is ideal because it can merge newly added land with adjacent land components in near-constant time.
m and n = grid dimensions, positions = land additions
number of islands after each addition
Example 1:
Input:
m = 3 n = 3 positions = [[0,0],[0,1],[1,2],[2,1],[1,1]]
Output:
[1,1,2,3,1]
Explanation:
Islands merge when the center land connects multiple existing components.
Example 2:
Input:
m = 1 n = 2 positions = [[0,0],[0,1]]
Output:
[1,1]
Explanation:
Two adjacent lands become a single island after the second addition.
Example 3:
Input:
m = 2 n = 2 positions = [[0,0],[1,1]]
Output:
[1,2]
Explanation:
The two lands are not adjacent, so they remain separate islands.