Given a directed graph with V vertices (0 .. V-1) and directed edges edges, a node is terminal if it has no outgoing edges, and safe if every path starting from it eventually reaches a terminal node (i.e. it can never get stuck in a cycle). Return all safe nodes in ascending order.
Input: V = 4, edges = [[0,1],[1,2],[2,0],[2,3]] Output: [3] 3 is terminal; 0,1,2 lie on a cycle.
Input: V = 7, edges = [[0,1],[0,2],[1,2],[2,3],[2,4],[3,5],[4,5]] Output: [0, 1, 2, 3, 4, 5, 6] No cycles, so every node is safe.
- 1 <= V <= 10^4 - 0 <= edges.length <= 4·10^4 - edges are directed u -> v - no duplicate edges
A node is safe iff it can't reach a cycle — every walk from it must dead-end at a terminal node. Two ways to find them:
3-state DFS. Colour nodes new / on-path / safe. A node is safe iff all its successors are safe; if DFS ever steps onto an on-path node, that's a cycle, so the node (and its ancestors on the path) are unsafe. Collect the safe-coloured nodes.
Kahn's on the reversed graph. Reverse every edge; a node's out-degree in the original becomes its in-degree here. Terminal nodes (out-degree 0) are safe, so peel them like Kahn's: a node becomes safe once all the nodes it pointed to are safe. This is topological sorting the "safe" frontier backwards. Both are O(V + E).
“What makes a node safe?”
Every path from it ends at a terminal node — it never enters a cycle.
“Output order?”
Ascending.
A node is safe when it can't reach a cycle, so I 3-state DFS and mark nodes whose every successor is safe.
Or I reverse the edges and run Kahn's from the terminal nodes outward.
Worked example — V = 4, edges [[0,1],[1,2],[2,0],[2,3]]
3 is terminal -> safe 0,1,2 sit on the cycle 0->1->2->0 -> unsafe answer = [3]
Every path from a safe node terminates.
One unsafe successor dooms it.
Out-degree 0 nodes seed the safe frontier.
| 3-state DFS | Reverse-graph Kahn | |
|---|---|---|
| Idea | safe iff no on-path successor | peel terminal nodes backward |
| Time | O(V+E) | O(V+E) |
| Output | sorted safe nodes | sorted safe nodes |
Both identify the same safe nodes. Full code is in the Approaches selector below.
Key takeaway
A node is safe iff it can't reach a cycle. 3-state DFS (safe = all successors safe), or reverse the edges and Kahn's from terminal nodes. Return them sorted. O(V+E).
dfs: safe(u) = every successor safe, and no on-path revisit kahn: reverse edges; terminals safe; node safe when out-degree hits 0
