Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for How to Find Friends by internom
def check_connection(network, first, second):
parent = {}
def find(x):
if x not in parent:
parent[x] = x
return parent[x]
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
for val in network:
f1, f2 = val.split('-')
# Merge without path compression
f1 = find(f1)
f2 = find(f2)
parent[f1] = f2
return find(first) == find(second)
if __name__ == '__main__':
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"scout2", "scout3") == True, "Scout Brotherhood"
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"super", "scout2") == True, "Super Scout"
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"dr101", "sscout") == False, "I don't know any scouts."
Dec. 4, 2015
