Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Group merging solution in Clear category for How to Find Friends by abe.dillon
from collections import defaultdict
def check_connection(network, first, second):
group = defaultdict(list)
for edge in network:
a, b = edge.split("-")
if a in group:
if b not in group:
group[b].append(group[a][0])
elif group[a][0] is not group[b][0]:
group[a][0] |= group[b][0] # merge group a and group b
group[b][0] = group[a][0]
else:
if b not in group:
group[b].append(set())
group[a].append(group[b][0])
group[a][0] |= {a, b}
return second in group[first][0]
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
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."
Feb. 2, 2015
