Approach Summary
A node is safe if all paths from it lead to a terminal (no cycle). DFS with 3-colour states: white/gray/black. Gray nodes are in a cycle.
How to Recognize This Pattern
- Nodes that cannot reach a cycle are "safe"
- 3-colour DFS: gray = in current path, black = confirmed safe
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V)
Tags
DFS BFS Graph Topological Sort