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 johan4622
def check_connection(network, first, second):
v_dict = {} ; v_number = 0 ; adjancy_list = []
# Crete Dictionry.
for e in network:
vs = e.split('-')
for v in vs:
if v not in list(v_dict.keys()):
v_dict[v] = v_number
adjancy_list.append([])
v_number += 1
v_keys = list(map(lambda x: v_dict[x], vs))
for i, j in zip(v_keys,v_keys[::-1]):
if i not in adjancy_list[j]:
adjancy_list[j].append(i)
# Check reachability
if first not in v_dict or second not in v_dict:
return False
candidates = [v_dict[first]] ; target = v_dict[second]
reached = [False] * len(adjancy_list)
while len(candidates) != 0:
c = candidates.pop()
reached[c] = True
if target in adjancy_list[c]:
return True # Found
elif len(adjancy_list[c]) != 0:
# Set next vertex
next_vs = [x for x in adjancy_list[c] if reached[x] == False]
candidates += next_vs
# else NOP
return False # Not Found
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."
Dec. 8, 2018
