Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Traverse tree from root solution in Clear category for What Is Wrong With This Family? by Sim0000
from collections import deque
from collections import defaultdict
def is_family(tree):
# find root
fathers, suns = map(set, zip(*tree))
roots = fathers - suns
if len(roots) != 1: return False
root = roots.pop()
n = len(fathers | suns)
# reconstruct tree
suns = defaultdict(list)
for father, sun in tree:
suns[father].append(sun)
# using BFS to trace a tree
seen = set() # visited node
q = deque([root])
while q:
node = q.popleft()
if node in seen: return False # found loop
seen.add(node)
if node in suns: q.extend(suns[node])
return len(seen) == n
# Traverse the graph from root and check for loops.
if __name__ == "__main__":
#These "asserts" using only for self-checking and not necessary for auto-testing
assert is_family([
['Logan', 'Mike']
]) == True, 'one father, one son'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack']
]) == True, 'two sons'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Alexander']
]) == True, 'grant father'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Logan']
]) == False, 'Can you be a father for your father?'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Jack']
]) == False, 'Can you be a father for your brather?'
assert is_family([
['Logan', 'William'],
['Logan', 'Jack'],
['Mike', 'Alexander']
]) == False, 'Looks like Mike is stranger in Logan\'s family'
print("Looks like you know everything. It is time for 'Check'!")
Jan. 8, 2021
Comments:
