Find Eventual Safe States | Leetcode 802 | DFS Solution

Learn how to list all “eventual safe” 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.

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

1. What does the problem ask?

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

A node is called eventual safe if every possible path that starts there always ends at a terminal node (a node with no outgoing edges). In other words, the node will never get stuck in a directed cycle.

Return all eventual safe nodes, sorted in ascending order.

2. Quick examples

(First row is LeetCode’s main sample.)

3. Deep intuition & approach

3.1 What makes a node unsafe?

If there is any path from that node that can loop forever, the node is unsafe.
So, in practice, cycles are the only danger. Every node that is inside a cycle or can reach a cycle is unsafe. All others are safe.

3.2 How to detect cycles quickly?

We run a Depth-First Search (DFS) with two helper arrays:

Think of the classic white → gray → black coloring:

1. When we first enter a node, we color it gray (path_vis = 1).
2. If we ever meet a neighbor that is already gray, we have a back edge → cycle!
3. When we finish exploring a node, we color it black (path_vis = 0).

3.3 Marking safe nodes

• If DFS finishes for a node without finding a back edge from it, that node, and all nodes on the successful path are guaranteed to be outside any cycle.
• We record this in an is_safe array so we never recalculate.

3.4 Why this works

A node cannot be both:

• on a path that enters a cycle and
• on a path that avoids every cycle

The DFS either returns False (cycle found on this route) or True (all outgoing paths proven safe). Memoization via vis and is_safe keeps the run linear.

4. Code Implementation

class Solution:
    # -------- helper DFS ----------
    def dfs(self, current_node, adj_list, vis, path_vis, is_safe):
        vis[current_node] = 1        # mark as visited (gray/black)
        path_vis[current_node] = 1   # mark as on current DFS path (gray)

        # explore every outward edge
        for adjNode in adj_list[current_node]:
            if vis[adjNode] == 0:                    # white node
                ans = self.dfs(adjNode, adj_list, vis, path_vis, is_safe)
                if ans == False:                     # cycle found deeper
                    return False
            elif path_vis[adjNode] == 1:             # back-edge to gray
                return False                         # direct cycle detected

        path_vis[current_node] = 0    # leave path (node turns black)
        is_safe[current_node] = 1     # no cycles via this node → safe
        return True

    # -------- main function ----------
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        V = len(graph)
        vis       = [0 for _ in range(V)]   # not processed yet
        path_vis  = [0 for _ in range(V)]   # not on current stack
        is_safe   = [0 for _ in range(V)]   # 0 = unknown / unsafe

        # launch DFS from every unvisited node
        for i in range(V):
            if vis[i] == 0:
                self.dfs(i, graph, vis, path_vis, is_safe)

        # collect all nodes proven safe
        result = []
        for i in range(V):
            if is_safe[i] == 1:
                result.append(i)
        return result

5. Line-by-line code walkthrough

1. vis, path_vis, is_safe initialised – all zeros.
2. Outer loop runs DFS on each component.
3. Inside dfs
   • Mark node visited & on path.
   • Iterate its neighbours:
     • Unvisited neighbour? Recurse.
     • Neighbour on path? Back edge → cycle → report False.
   • If loop finishes, clear path_vis & label node safe.
   • Return True so callers know this sub-path is clean.
4. After all DFS calls, we scan is_safe and return indices that are 1.

Because is_safe is set only when a node’s every outgoing route is safe, the result list matches the definition perfectly.

6. Dry run on LeetCode’s sample

Graph
[[1,2],[2,3],[5],[0],[5],[],[]]
Number nodes 0-6.

But we can summarise in prose.

We’ll include explanation of detection.

7. Complexity analysis

8 Conclusion

• Eventual safe nodes are simply nodes not tied to any directed cycle.
• A DFS with path tracking spots cycles on the fly.
• By caching results in is_safe, we avoid duplicate work and keep the run linear.

If you prefer an iterative style, the same task can be done with reverse BFS / topological sort (Kahn’s algorithm on the reversed graph). Yet the recursive method above is short, clear, and perfect for teaching how cycle detection relates to safety in directed graphs.

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