Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
depth-first search solution in Clear category for Network Loops by David_Jones
from collections import defaultdict
def find_cycle(connections):
largest_cycle = (0,) * 3
G = defaultdict(set)
for (u,v) in connections:
G[u].add(v)
G[v].add(u)
stack = [(u,) for u in G]
while stack:
path = stack.pop()
for u in G[path[-1]]:
if u not in path:
stack.append(path + (u,))
elif u == path[0] and len(path) >= len(largest_cycle):
largest_cycle = path + (u,)
return largest_cycle if len(largest_cycle) > 3 else ()
June 12, 2019
