ShiYu

# 第15节 并查集及其相关题目

# 并查集

  • 有若干个样本a、b、c、d…类型假设是V
  • 在并查集中一开始认为每个样本都在单独的集合里
  • 用户可以在任何时候调用如下两个方法：
    • boolean isSameSet(V x, V y) :查询样本x和样本y是否属于一个集合
    • void union(V x, V y) :把x和y各自所在集合的所有样本合并成一个集合
  • isSameSet和union方法的代价越低越好

# 并查集

  • 每个节点都有一条往上指的指针
  • 节点a往上找到的头节点，叫做a所在集合的代表节点
  • 查询x和y是否属于同一个集合，就是看看找到的代表节点是不是一个
  • 把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂在大集合的代表点的下方即可

# 并查集的优化

  • 节点往上找代表点的过程，把沿途的链变成扁平的，往上找链路时，将所有链路指向代表节点
  • 小集合挂在大集合的下面
  • 如果方法调用很频繁，那么单次调用的代价为O(1)，两个方法都如此

代码：
1

# 并查集的应用

  • 解决两大块区域的合并问题
  • 常用在图等领域中

# 并查集应用相关题目

leetcode-547省份数量 (opens new window)

有 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
1
2

示例 2：

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

提示：

  • 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]

代码：
1

# 并查集应用相关题目

岛问题 给定一个二维数组matrix，里面的值不是1就是0， 上、下、左、右相邻的1认为是一片岛， 返回matrix中岛的数量

实现版本一：感染版本

实现版本二：并查集不优化版本

实现版本三：并查集优化版本

代码：
1

# 并查集应用相关题目

岛问题（扩展）305. Number of Islands II

动态并查集

代码：
1

# 并查集应用相关题目

岛问题（扩展） 如果matrix极大，设计一种可行的并行计算方案

代码：
1

← 第16节 图 →