并查集

基础数据结构(二) — Union Find并查集

按节点数量进行优化按节点的高度进行优化

305. 岛屿数量 II

给你一个大小为 m x n 的二进制网格 grid 。网格表示一个地图，其中，0 表示水，1 表示陆地。最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。
可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。
返回一个整数数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后，地图中岛屿的数量。
岛屿 的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。
示例 1：
输入：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 个岛屿。
示例 2：
输入：m = 1, n = 1, positions = [[0,0]] 输出：[1]

提示：

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

进阶：你可以设计一个时间复杂度 O(k log(mn)) 的算法解决此问题吗？（其中 k == positions.length）
通过次数4,198
提交次数11,070

剑指 Offer II 116. 朋友圈

一个班上有 n 个同学，其中一些彼此是朋友，另一些不是。朋友关系是可以传递的，如果 a 与 b 直接是朋友，且 b 与 c 是直接朋友，那么 a 与 c 就是间接朋友。
定义 朋友圈 就是一组直接或者间接朋友的同学集合。
给定一个 n x n 的矩阵 isConnected 表示班上的朋友关系，其中 isConnected[i][j] = 1 表示第 i 个同学和第 j 个同学是直接朋友，而 isConnected[i][j] = 0 表示二人不是直接朋友。
返回矩阵中 朋友圈的数量。

示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出：2

示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出：3

提示：

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] 为 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]