Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS solution in Clear category for How to Find Friends by MrAnderson
def check_connection(friends, a, b):
names = _get_unique_names(friends)
graph = Graph()
for name in names:
graph.vertices[name] = Vertex(name)
for i in friends:
graph.check_if_edge(i[:i.find('-')], i[i.find('-') + 1:])
graph.dfs(graph.vertices.get(a))
return graph.vertices.get(b).color != 'black'
def _get_unique_names(names):
_names = set()
for i in names:
_names.add(i[:i.find('-')])
_names.add(i[i.find('-') + 1:])
return _names
class Graph():
vertices = {}
def _dfs(self, vertex):
vertex.color = 'red'
print('current vertex', vertex.name, vertex.color, vertex.neighbors)
for v in vertex.neighbors:
if self.vertices[v].color == 'black':
self._dfs(self.vertices[v])
vertex.color = 'blue'
print('current vertex', vertex.name, vertex.color)
def dfs(self, vertex):
self._dfs(vertex)
def check_if_edge(self, u, v):
if u in self.vertices and v in self.vertices:
for key, value in self.vertices.items():
if key == u:
value.add_neighbor(v)
if key == v:
value.add_neighbor(u)
class Vertex():
def __init__(self, n):
self.name = n
self.neighbors = list()
self.color = 'black'
self.discovery = False
def add_neighbor(self, v):
if v not in self.neighbors:
self.neighbors.append(v)
self.neighbors.sort()
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."
Nov. 21, 2018
