Learn how to list all \u201ceventual safe\u201d nodes in a directed graph. We use DFS with path-tracking to spot cycles and mark safe nodes. Includes easy examples, fully-commented Python code, dry run, and Big-O analysis.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n You are given a directed graph as an adjacency list A node is called eventual safe<\/strong> if every<\/strong> possible path that starts there always<\/strong> ends at a terminal node (a node with no outgoing edges). In other words, the node will never<\/strong> get stuck in a directed cycle.<\/em><\/p>\n\n\n\n Return all eventual safe nodes<\/strong>, sorted in ascending order.<\/p>\n\n\n\n (First row is LeetCode\u2019s main sample.)<\/em><\/p>\n\n\n\n If there is any<\/em> path from that node that can loop forever, the node is unsafe. We run a Depth-First Search (DFS)<\/strong> with two helper arrays:<\/p>\n\n\n\n Think of the classic white \u2192 gray \u2192 black<\/em> coloring:<\/p>\n\n\n\n A node cannot be both:<\/p>\n\n\n\n The DFS either returns 1. What does the problem ask?<\/h2>\n\n\n\n
graph<\/code>, wheregraph[i]<\/code> holds every node you can reach directly<\/strong> from node i<\/code>.<\/p>\n\n\n\n
\n\n\n\n2. Quick examples<\/h2>\n\n\n\n
graph<\/code><\/th>Safe nodes<\/th> Why<\/th><\/tr><\/thead> [[1,2],[2,3],[5],[0],[5],[],[]]<\/code><\/td>[2,4,5,6]<\/code><\/td>Nodes 0,1,3<\/code> lead into the cycle 0\u21921\u21922\u2192\u2026<\/code>? Wait, not exactly; show cycle. Node 2<\/code> reaches 5<\/code> (terminal) with no cycle, 4<\/code>\u21925<\/code>, 5<\/code> and 6<\/code> are terminals.<\/td><\/tr>[[],[0,2,3,4],[3],[],[3]]<\/code><\/td>[0,1,2,3,4]<\/code><\/td>Graph has no<\/strong> cycles; every node is safe.<\/td><\/tr> [[1,2,3], [2,3], [3], [0]]<\/code><\/td>[]<\/code><\/td>There is a big cycle; no node can escape.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n3. Deep intuition & approach<\/h2>\n\n\n\n
3.1 What makes a node unsafe<\/strong>?<\/h3>\n\n\n\n
So, in practice, cycles<\/strong> are the only danger. Every node that is inside<\/strong> a cycle or can reach<\/strong> a cycle is unsafe. All others are safe.<\/p>\n\n\n\n3.2 How to detect cycles quickly?<\/h3>\n\n\n\n
Name<\/th> Meaning during DFS<\/th><\/tr><\/thead> vis<\/code><\/td>1 \u2192 node has been processed at least once<\/td><\/tr> path_vis<\/code><\/td>1 \u2192 node lies on the current<\/strong> recursion stack (the active path)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n \n
path_vis = 1<\/code>).<\/li>\n\n\n\npath_vis = 0<\/code>).<\/li>\n<\/ol>\n\n\n\n3.3 Marking safe<\/strong> nodes<\/h3>\n\n\n\n
\n
is_safe<\/code> array so we never recalculate.<\/li>\n<\/ul>\n\n\n\n3.4 Why this works<\/h3>\n\n\n\n
\n
False<\/code><\/strong> (cycle found on this route) or True<\/code><\/strong> (all outgoing paths proven safe). Memoization via vis<\/code> and is_safe<\/code> keeps the run linear.<\/p>\n\n\n\n
\n\n\n\n4. Code Implementation<\/h2>\n\n\n\n