Find Eventual Safe States | Leetcode 802 | Kahn’s Algorithm (BFS) Solution

We flip the graph, run Kahn’s 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.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

You get a directed graph as an adjacency list graph, where graph[i] contains every node you can reach directly from node i.

• A node is eventual safe if every path that starts there eventually ends at a terminal node (a node with no outgoing edges).
• If even one path can spin forever inside a cycle, the start node is not safe.

Return all safe nodes in ascending order.

2. What we need to do?

Imagine marbles rolling along the arrows.
If a marble starting at node x might whirl around a loop forever, x is unsafe.
If every marble that ever starts at x always falls off the board at a dead-end, x is safe.

So: “Safe” = cannot reach a directed cycle.

Also check Topological Sort (Kahn’s Algorithm)

3. Intuition & Approach – BFS / Kahn’s way

3.1 Why reverse the graph?

The dangerous objects are cycles.
Terminal nodes (out-degree 0) are certainly safe, because a marble there is already at rest.
If you can only reach terminal or already-safe nodes, you are safe too.

That logic points backwards:

• From a safe node, every predecessor that points into it might also be safe.

Reversing all arrows turns “predecessor” into “successor”, which is perfect for BFS.

3.2 Build the reversed graph

For every original edge u → v we insert v ← u.
Now an arrow means “this node depends on that neighbour still being proven safe”.

3.3 Kahn’s topological idea in this setting

1. Indegree = how many outgoing edges the node had in the original graph.
   In the reversed graph it tells us how many neighbours are blocking the node from being called safe.
2. Queue start: every terminal node (indegree 0) is already safe.
3. BFS loop:
   • Pop a safe node.
   • For each predecessor in the reversed graph, lower its indegree.
   • When a predecessor’s indegree hits 0, all its original edges now lead to known-safe nodes, so the predecessor itself becomes safe; push it into the queue.
4. Finish: every node we popped is safe. Sort the list and return it.

3.4 Why it guarantees correctness

Kahn’s algorithm deletes edges layer by layer.
If a node ever reaches indegree 0, none of its original edges point to a cycle any more.
Nodes trapped in or feeding into a cycle will always keep at least one edge pointing inside that loop, so their indegree never reaches 0, and they never enter the queue.

4. Code

from collections import deque
from typing import List     # for type hinting only

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        V = len(graph)

        # -------- 1. Build reversed adjacency list --------
        adj_list = [[] for _ in range(V)]          # reversed graph
        for node in range(V):
            for adjNode in graph[node]:            # original edge node -> adjNode
                adj_list[adjNode].append(node)     # reversed edge adjNode -> node

        # -------- 2. Compute indegree array (original out-degrees) --------
        indegrees = [0] * V
        for node in range(V):
            for adjNode in adj_list[node]:
                indegrees[adjNode] += 1            # edge points *into* adjNode

        # -------- 3. Queue initial safe nodes (terminal nodes) --------
        queue = deque()
        for node in range(V):
            if indegrees[node] == 0:               # no outgoing edges originally
                queue.append(node)

        # -------- 4. BFS to peel off safe layers --------
        result = []
        while queue:
            node = queue.popleft()
            result.append(node)                    # node confirmed safe
            for adjNode in adj_list[node]:         # visit predecessors
                indegrees[adjNode] -= 1            # remove supporting edge
                if indegrees[adjNode] == 0:        # all outgoing paths now safe
                    queue.append(adjNode)

        # -------- 5. Return sorted list of safe nodes --------
        result.sort()
        return result

5. Step-by-step code explanation

1. Reverse the arrows so we can move backwards from terminals.
2. indegrees now counts how many original outgoing edges each node still has that are not yet proven safe.
3. Initial queue collects every terminal node (indegree 0). They are safe by definition.
4. BFS loop
   • Pop the next safe node.
   • “Delete” its contribution to each predecessor by subtracting from indegree.
   • If a predecessor’s indegree drops to zero, absolutely all its original edges now lead to safe nodes, so we mark it safe too.
5. Sorting – BFS pops nodes in topological order of the reversed graph, which is not necessarily ascending numeric order, so we sort before returning.

6. Dry run on LeetCode’s sample

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Sort → [0,1,2,4,5,6] (matches the official answer).

7. Complexity analysis

V = number of nodes, E = number of edges.

8. Conclusion

• Reversing the graph and running Kahn’s topological BFS peels off “safe layers” from the terminal nodes outward.
• Every node that eventually reaches indegree 0 is guaranteed not to touch a cycle.
• The method is linear, easy to code, and a great alternative to the DFS back-edge technique when you prefer an iterative approach.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.