DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Find Eventual Safe States

mediumGraphs

Problem statement

You get a directed graph with n nodes labelled 0 to n - 1, as a list graph where graph[i] holds the nodes that node i has an edge to.

A node with no outgoing edges is a terminal node. A node is safe if every possible path starting from it eventually ends at a terminal node; in other words, no path from it can get stuck going round a cycle.

Return all safe nodes in ascending order.

Examples

Example 1

Input: graph = [[1, 2], [2], [], [0, 4], [4]]

Output: [0, 1, 2]

Explanation: Node 2 is terminal. Nodes 0 and 1 can only lead to 2. Node 4 points to itself, a cycle, and node 3 can go to 4, so both are unsafe.

Example 2

Input: graph = [[1], [2], [0, 3], []]

Output: [3]

Explanation: 0 -> 1 -> 2 -> 0 is a cycle, so 0, 1 and 2 are unsafe even though 2 also has an edge to the terminal node 3.

Hints

Approach

Peel safe nodes off from the terminals backwards, like a topological sort on the reversed graph.

  1. Build the reverse graph: for each edge u -> v, record u in parents[v]. Let outdeg[u] be the number of edges leaving u.
  2. Queue every node with outdeg == 0 (the terminals). They are safe.
  3. Pop a safe node v. For each parent u, one more of its edges is now known to lead somewhere safe, so decrement outdeg[u]. When it hits zero, every edge from u leads to a safe node, so u is safe: queue it.
  4. Nodes that never reach zero have an edge that leads, directly or indirectly, into a cycle. Return the safe nodes in index order.

Every node is queued at most once and every edge is relaxed once. Nothing recurses, so deep graphs are fine.

ComplexityTime O(V + E)Space O(V + E)
Python
from collections import deque
class Solution:
def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:
n = len(graph)
parents = [[] for _ in range(n)]
outdeg = [0] * n
for u in range(n):
outdeg[u] = len(graph[u])
for v in graph[u]:
parents[v].append(u)
queue = deque(u for u in range(n) if outdeg[u] == 0)
safe = [False] * n
while queue:
v = queue.popleft()
safe[v] = True
for u in parents[v]:
outdeg[u] -= 1
if outdeg[u] == 0: # every edge from u leads to a safe node
queue.append(u)
return [i for i in range(n) if safe[i]]

Follow-up questions

  • Return the cycles themselves, not just the unsafe nodes.
  • Edges are added over time. How would you keep the safe set up to date?

Frequently asked questions

Yes: keep the colours across all starts instead of resetting them. A node that finished black is safe, and a node left grey when a cycle was found stays grey and is unsafe. That memoised three-colour DFS is also O(V + E), but it recurses, which can hit Python's recursion limit on long chains; the reverse-graph queue does not.

It is deadlock and loop analysis. Given a graph of which job waits on which, or which service retries into which, the unsafe nodes are the ones that can end up waiting forever in a cycle. The same check finds redirect loops, circular module imports, or workflow states that can never reach a finished state.