leetcode：305. 岛屿的数量

题目来源

• leetcode

题目描述

假设你设计一个游戏，用一个 m 行 n 列的 2D 网格来存储你的游戏地图。html

起始的时候，每一个格子的地形都被默认标记为「水」。咱们能够经过使用 addLand 进行操做，将位置 (row, col) 的「水」变成「陆地」。

你将会被给定一个列表，来记录全部须要被操做的位置，而后你须要返回计算出来 每次 addLand 操做后岛屿的数量。网络

注意：一个岛的定义是被「水」包围的「陆地」，经过水平方向或者垂直方向上相邻的陆地链接而成。

输入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
输出：[1,1,2,3]
解释：
起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」）
- 操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。此时存在 1 个岛屿。
- 操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。此时存在 1 个岛屿。
- 操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。此时存在 2 个岛屿。
- 操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。此时存在 3 个岛屿。

题目解析

并查集

和其他的不同是，这里的并查集是动态生成的