并查集连了两次之后
五个点各自一块。先 union(0, 2),再 union(3, 4)。运行下面这段程序,看三件事:0 和 2 连通了吗、0 和 3 连通了吗、现在还剩几块:
def make(verts):
return {u: u for u in verts}
def find(p, x):
while p[x] != x:
p[x] = p[p[x]]
x = p[x]
return x
def union(p, a, b):
ra, rb = find(p, a), find(p, b)
if ra == rb:
return False
p[ra] = rb
return True
p = make([0, 1, 2, 3, 4])
union(p, 0, 2)
union(p, 3, 4)
print(str(find(p, 0) == find(p, 2)) + "/" + str(find(p, 0) == find(p, 3)) + "/" + str(len({find(p, u) for u in [0, 1, 2, 3, 4]})))
全部评论