代码随想录算法训练营第53天｜107. 寻找存在的路径(并查集)

并查集主要用来判断是不是联通的。

107. 寻找存在的路径

卡码网 107. 寻找存在的路径
代码随想录

class unionFind():def __init__(self, size):self.parent = list(range(size+1))def find(self, u):if self.parent[u] != u:# 如果这个节点不是根节点，把这个节点的就去找这个节点的父节点，只到找到一个根节点self.parent[u] = self.find(self.parent[u])return self.parent[u]def union(self, u, v):root_u = self.find(u)root_v = self.find(v)if root_u != root_v:self.parent[root_v] = root_udef is_same(self, u, v):return self.find(u) == self.find(v)n, m = map(int,input().split())union_set = unionFind(n)for _ in range(m):s,t = map(int,input().split())union_set.union(s,t)s,t = map(int,input().split())if union_set.is_same(s,t):print(1)
else:print(0)