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
- A node is safe iff none of its reachable nodes lies on a cycle.
- Use the three-colour DFS: 1 = on the current path, 2 = verified safe.
- Encountering a colour-1 node means a cycle, so the current node is unsafe.
- 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.