上一篇教程:快速傅里叶变换 ↑
下一篇教程:支持随机访问的堆 ↓
相关类 rm::UnionFind
并查集是一种树型的数据结构,用于处理一些不相交集合的 合并 及 查询 问题,常常在使用中用森林来表示。
在一些有 N
个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。
使用森林来表示的并查集,查询、合并操作时间复杂度均接近 \(\text O(1)\)。
rm::UnionFind 支持集合的快速合并、查找的结构,提供三种典型操作
成员方法 | 含义 |
---|---|
bool connected(a, b); | 两个元素是否在一个集合中 |
void merge(a, b); | 两个元素所在集合进行合并 |
void components(a, b); | 获取并查集的连通分量 |
【LeetCode 200】岛屿数量
问题:
给你一个由 ‘'1’(陆地)和
'0'`(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
示例 2:
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
的值为 ‘'0’或
'1'`代码:
使用 UnionFind 进行解答: