Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
OOP solution in Clear category for How to Find Friends by ZoltanOnody
#Todo: implement union-find
class Union:
def __init__(self, network):
self.graph = []
self.ids = {}
self.id = 0
for connection in network:
a, b = connection.split('-')
self.add(a,b)
def add(self, a, b):
if a not in self.ids.keys():
self.ids[a] = self.id
self.graph.append(self.id)
self.id += 1
if b not in self.ids.keys():
self.ids[b] = self.id
self.graph.append(self.id)
self.id += 1
# values that sholud be replaced...
a = self.graph[self.ids[a]]
b = self.graph[self.ids[b]]
for i in range(len(self.graph)):
if self.graph[i] == a:
self.graph[i] = b
def connected(self, first, second):
return self.graph[self.ids[first]] == self.graph[self.ids[second]]
def check_connection(network, first, second):
union = Union(network)
return union.connected(first, second)
Jan. 17, 2015
