DiffPush Tier Graphs · MST Problems O(k α(n * m)) · O(n * m)
A dredging simulator turns single sea cells into land one command at a time, and hydrology wants the live island count after every command — islands being land patches joined side-to-side. Each new cell either opens its own island or bridges up to four neighbouring islands into one, so a union-find ledger keeps the running tally without rescanning the basin.
Input: Integers n, m (an n x m basin, initially all water) and a list operators of [row, col] landfall commands.
Output: Return an array holding the number of islands after each operation.
1 <= n, m <= 10^31 <= operators.length <= 10^40 <= row < n, 0 <= col < mInput: {"n":4,"m":5,"operators":[[1,1],[0,1],[3,3],[3,4]]}
Output: [1,1,2,2]
The first two cells stack into one island; the two bottom-right cells form a second.
Input: {"n":3,"m":3,"operators":[[0,0],[0,0]]}
Output: [1,1]
Re-filling an already-land cell changes nothing.