Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
union-find tree solution in Clear category for How to Find Friends by cnkisk
def check_connection(network, first, second):
from collections import defaultdict
p = defaultdict(int)
def find(user):
if p[user] == 0:
return user
else:
p[user] = find(p[user])
return p[user]
def unite(x,y):
if find(x) == find(y):
pass
else:
p[find(x)] = find(y)
for n in network:
f, s = n.split("-")
unite(f,s)
print(f"answer : {first}'s parent is {find(first)}, {second}'s parent is {find(second)}")
return find(first) == find(second)
May 14, 2021