代码随想录算法训练营Day59

并查集理论基础
力扣1971.寻找图中是否存在路径【easy】

一、并查集理论基础

文档链接：代码随想录

1、并查集

作用

• 将两个元素添加到一个集合中。
• 判断两个元素在不在同一个集合

路径压缩

• 如果这棵多叉树高度很深的话，每次find函数 去寻找根的过程就要递归很多次。
• 我们的目的只需要知道这些节点在同一个根下就可以，所以对这棵多叉树的构造只需要这样就可以了，如图：

按秩合并

• 目标：合并两个集合的根节点。
• 总是将小树（高度低）合并到大树（高度高）的根下，避免树的高度过高。

2、代码

• find：压缩路径

def find(self, x):if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])  # 递归找根，并更新父节点return self.parent[x]

• union：秩合并

  def union(self, x, y):root_x = self.find(x)root_y = self.find(y)if root_x == root_y:return  # 已在同一集合# 按秩合并：小树合并到大树if self.rank[root_x] < self.rank[root_y]:self.parent[root_x] = root_yelse:self.parent[root_y] = root_xif self.rank[root_x] == self.rank[root_y]:self.rank[root_x] += 1  # 树高度+1

---

二、力扣1971.寻找图中是否存在路径【easy】

题目链接：力扣1971.寻找图中是否存在路径

视频链接：代码随想录
题解链接：力扣

1、思路

• 时间复杂度：$O(n+m)$

2、代码

• 并查集

class Solution:def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:def find(x):if p[x] != x:p[x] = find(p[x])return p[x]p = list(range(n))for u, v in edges:p[find(u)] = find(v)return find(source) == find(destination)

• dfs

class Solution:def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:def dfs(i):if i == destination:return Truevis.add(i)for j in g[i]:if j not in vis and dfs(j):return Truereturn Falseg = defaultdict(list)for a, b in edges:g[a].append(b)g[b].append(a)vis = set()return dfs(source)

---