Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Union-find solution in Speedy category for How to Find Friends by nickie
def check_connection(network, first, second):
# A modest implementation of union-find
parent = {}
rank = {}
def union(x, y):
xRoot = find(x)
yRoot = find(y)
if xRoot == yRoot:
return
if rank.get(xRoot, 0) < rank.get(yRoot, 0):
parent[xRoot] = yRoot
elif rank.get(xRoot, 0) > rank.get(yRoot, 0):
parent[yRoot] = xRoot
else:
parent[yRoot] = xRoot
rank[xRoot] = rank.get(xRoot, 0) + 1
def find(x):
if x not in parent:
return x
parent[x] = find(parent[x])
return parent[x]
# Now let's rock...
for connection in network:
[u, v] = connection.split("-")
union(u, v)
if find(first) == find(second):
return True
return False
Aug. 30, 2014
