Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for How to Find Friends by Moff
class QuickFindUF(object):
def __init__(self):
self.key = dict()
def push(self, p):
if p not in self.key:
self.key[p] = len(self.key) + 1
def connected(self, p, q):
return self.key.get(p) == self.key.get(q)
def union(self, p, q):
self.push(p)
self.push(q)
if self.connected(p, q):
return
pkey = self.key[p]
for node, key in self.key.items():
if key == pkey:
self.key[node] = self.key[q]
def check_connection(pairs, name1, name2):
uf = QuickFindUF()
for pair in pairs:
uf.union(*pair.split('-'))
return uf.connected(name1, name2)
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."
July 17, 2015