We flip the graph, run Kahn\u2019s topological BFS, and list every node guaranteed to avoid cycles. Includes clear intuition, step-by-step code walk-through, dry run, and full Python code with comments.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n You get a directed graph as an adjacency list Return all safe nodes in ascending order<\/strong>.<\/p>\n\n\n\n Imagine marbles rolling along the arrows.1. What does the problem ask?<\/h2>\n\n\n\n
graph<\/code>, where graph[i]<\/code> contains every node you can reach directly<\/strong> from node i<\/code>.<\/p>\n\n\n\n\n
\n\n\n\n2. What we need to do?<\/h2>\n\n\n\n
If a marble starting at node x<\/code> might whirl around a loop forever, x<\/code> is unsafe.
If every marble that ever starts at x<\/code> always falls off the board at a dead-end, x<\/code> is safe.<\/em><\/p>\n\n\n\n