1059. All Paths from Source Lead to Destination

• Time: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{edges}|$
• Space: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{edges}|$
  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 32 33 34 enum class State { kInit, kVisiting, kVisited }; class Solution { public: bool leadsToDestination(int n, vector>& edges, int source, int destination) { vector> graph(n); vector states(n); for (const vector& edge : edges) graph[e[0]].push_back(e[1]); return acyclic(graph, source, destination, states); } private: bool acyclic(const vector>& graph, int u, int dest, vector& states) { if (graph[u].empty()) return u == dest; if (states[u] == State::kVisiting) return false; if (states[u] == State::kVisited) return true; states[u] = State::kVisiting; for (const int v : graph[u]) if (!acyclic(graph, v, dest, states)) return false; states[u] = State::kVisited; return true; } }; 
  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 32 33 enum State { kInit, kVisiting, kVisited } class Solution { public boolean leadsToDestination(int n, int[][] edges, int source, int destination) { List[] graph = new List[n]; State[] states = new State[n]; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] edge : edges) graph[e[0]].add(e[1]); return acyclic(graph, source, destination, states); } private boolean acyclic(List[] graph, int u, int dest, State[] states) { if (graph[u].isEmpty()) return u == dest; if (states[u] == State.kVisiting) return false; if (states[u] == State.kVisited) return true; states[u] = State.kVisiting; for (final int v : graph[u]) if (!acyclic(graph, v, dest, states)) return false; states[u] = State.kVisited; return true; } }