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 radekj
from collections import defaultdict
def find_connection(graph, first, second, path):
"""
Recursive function for processing all nodes in graph
in search of connection between first and second nodes
"""
path = path + [first]
if first == second:
return path
if not first in graph:
return None
for node in graph[first]:
if node not in path:
newpath = find_connection(graph, node, second, path)
return newpath if newpath else None
def check_connection(network, first, second):
# build graph
graph = defaultdict(list)
for friends in network:
name1, name2 = friends.split('-')
graph[name1].append(name2)
graph[name2].append(name1)
return True if find_connection(graph, first, second, path=[]) else False
April 5, 2015
