Nodes Clear of Cycles
Problem
A build system has n steps numbered 0 to n - 1, and graph[i] lists the steps that step i hands off to, as a directed graph. A step is safe when every chain of hand-offs starting from it eventually stops, which means no chain from it can reach a cycle. Return the safe steps in increasing order. A step that hands off to itself forms a cycle.
Examples
Input: graph = [[1, 2], [2], [3], [], [5], [4], [3, 4]]
Output: [0, 1, 2, 3]
Why: 4 and 5 hand off to each other forever, and 6 can reach themInput: graph = [[], [0], [1]]
Output: [0, 1, 2]
Why: every chain ends at step 0, which hands off to nobodyInput: graph = [[0]]
Output: []
Why: edge case, the only step loops back to itselfHints
0 / 3
A step is unsafe exactly when some cycle is reachable from it. You need to know whether a depth-first search from a step ever runs into a cycle.
One visited set cannot tell a finished step from one that is still open on the current path. Three colours can, and an edge into an open step means a cycle.
Colour a step grey when you enter it and explore its hand-offs. If any hand-off reaches a grey step, or a step already known to be unsafe, stop and leave the current step grey, which now means unsafe. If all hand-offs finish safely, colour it black. The black steps are the answer.
Solution
This is the three-colour cycle search with its colours reused as a memo. A step turns black only after every step it can reach has turned black, so black means no cycle is reachable. A search that meets a grey step has found a back edge, and every step on the current path can reach that cycle, so those steps are left grey for good and later searches treat grey as unsafe. Every step and edge is handled once, so time is O(n + e) for e hand-offs, and space is O(n) for the colours and the recursion.
def safe_steps(graph):
WHITE, GREY, BLACK = 0, 1, 2
colour = [WHITE] * len(graph)
def safe(u):
if colour[u] != WHITE:
return colour[u] == BLACK # grey: on the path now, or proven unsafe
colour[u] = GREY
for v in graph[u]:
if not safe(v):
return False # u stays grey: it reaches a cycle
colour[u] = BLACK
return True
return [u for u in range(len(graph)) if safe(u)]
print(safe_steps([[1, 2], [2], [3], [], [5], [4], [3, 4]])) # -> [0, 1, 2, 3]
print(safe_steps([[], [0], [1]])) # -> [0, 1, 2]
print(safe_steps([[0]])) # -> []Stuck on the idea rather than the code? Cycles in a Directed Graph covers it.