# 802. Find Eventual Safe States      • Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 enum class State { kInit, kVisiting, kVisited }; class Solution { public: vector eventualSafeNodes(vector>& graph) { vector ans; vector state(graph.size()); for (int i = 0; i < graph.size(); ++i) if (!hasCycle(graph, i, state)) ans.push_back(i); return ans; } private: bool hasCycle(const vector>& graph, int u, vector& state) { if (state[u] == State::kVisiting) return true; if (state[u] == State::kVisited) return false; state[u] = State::kVisiting; for (const int v : graph[u]) if (hasCycle(graph, v, state)) return true; state[u] = State::kVisited; return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 enum State { kInit, kVisiting, kVisited } class Solution { public List eventualSafeNodes(int[][] graph) { List ans = new ArrayList<>(); State[] state = new State[graph.length]; for (int i = 0; i < graph.length; ++i) if (!hasCycle(graph, i, state)) ans.add(i); return ans; } private boolean hasCycle(int[][] graph, int u, State[] state) { if (state[u] == State.kVisiting) return true; if (state[u] == State.kVisited) return false; state[u] = State.kVisiting; for (final int v : graph[u]) if (hasCycle(graph, v, state)) return true; state[u] = State.kVisited; return false; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 from enum import Enum class State(Enum): kInit = 0 kVisiting = 1 kVisited = 2 class Solution: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: state = [State.kInit] * len(graph) def hasCycle(u: int) -> bool: if state[u] == State.kVisiting: return True if state[u] == State.kVisited: return False state[u] = State.kVisiting if any(hasCycle(v) for v in graph[u]): return True state[u] = State.kVisited return [i for i in range(len(graph)) if not hasCycle(i)]