⚡Flashcard Drill➔
NeetCode #574LC-802MediumGraphs
← Back to All Problems

#574 · #802 · Find Eventual Safe States(找到最终的安全状态)

📌 Problem Statement & Constraints

There is a directed graph of n nodes where graph[i] lists the nodes reachable from i. A node is safe if every possible path starting there eventually reaches a terminal node (a node with no outgoing edges). Return all safe nodes in ascending order. Constraints: 1 <= n <= 10^4, 0 <= graph[i].length <= n.

💡 Core Algorithmic Approaches

  1. A node is safe iff none of its reachable nodes lies on a cycle.
  2. Use the three-colour DFS: 1 = on the current path, 2 = verified safe.
  3. Encountering a colour-1 node means a cycle, so the current node is unsafe.
  4. Collect the nodes verified safe (colour 2).

💻 Benchmark Python3 Implementation

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        state = [0] * n                    # 0 = unvisited, 1 = on stack, 2 = safe

        def dfs(node: int) -> bool:
            if state[node] == 1:
                return False               # back edge -> cycle
            if state[node] == 2:
                return True                # already verified
            state[node] = 1
            for nxt in graph[node]:
                if not dfs(nxt):
                    return False
            state[node] = 2
            return True

        return [i for i in range(n) if dfs(i)]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(V + E): each node and edge is visited once.
💾 Space Complexity
O(V) for the state array plus the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Using a single boolean visited flag: a node on the current path must be distinguished from a fully verified one.
  • Marking safe before exploring all successors: a later successor might reveal a cycle.
  • Running a separate reachability check per node: O(V * (V + E)).
  • Returning the nodes in DFS order: the problem requires ascending order, which the final comprehension gives.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems