代码随想录算法训练营第55天|并查集理论基础、107. 寻找存在的路径

1. 并查集理论基础

文档讲解： 代码随想录

并查集主要有两个功能：将两个元素添加到一个集合中，判断两个元素是否在同一个集合中。空间复杂度为 $O(n)$，路径压缩后的并查集时间复杂度在 $O(logn)$ 与 $O(1)$ 之间，且随着查询或者合并操作的增加，会越来越趋于 $O(1)$。

2. 107. 寻找存在的路径

题目链接：107. 寻找存在的路径
文档讲解： 代码随想录

#定义寻根函数
def find(u):if father[u] == u:return u else:#路径压缩father[u] = find(father[u])return father[u]
#判断u和v是否同根
def issame(u,v):u = find(u)v = find(v)return u == v
#将v -> u 这条边加入并查集
def joinside(u,v):u = find(u)v = find(v)if u == v:return father[v] = u 
n,m = map(int,input().split())
father = [0] * (n+1)
#并查集初始化
for i in range(n+1):father[i] = i 
for _ in range(m):s,t = map(int,input().split())joinside(s,t) 
source,destination = map(int,input().split())
res = issame(source,destination)
if res:print(1)
else:print(0)