代码随想录算法训练营 Day 47
Published:
并查集
并查集常用来解决连通性问题，主要的两个功能：1. 将两个元素添加到一个集合中；2. 判断两个元素在不在同一个集合中
Q1. KamaCoder 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):
u = self.find(u)
v = self.find(v)
if u != v:
self.parent[v] = u
def is_same(self, u, v):
return self.find(u) == self.find(v)
if __name__ == '__main__':
n, m = map(int, input().split())
uf = UnionFind(n)
edge = []
for _ in range(m):
s, t = map(int, input().split())
uf.union(s, t)
source, destination = map(int, input().split())
if uf.find(source) == uf.find(destination):
print(1)
else:
print(0)