Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

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}|$

			


enum class State { kInit, kVisiting, kVisited };

class Solution {
 public:
  bool leadsToDestination(int n, vector<vector<int>>& edges, int source,
                          int destination) {
    vector<vector<int>> graph(n);
    vector<State> state(n);

    for (const vector<int>& e : edges)
      graph[e[0]].push_back(e[1]);

    return acyclic(graph, source, destination, state);
  }

 private:
  bool acyclic(const vector<vector<int>>& graph, int u, int dest,
               vector<State>& state) {
    if (graph[u].empty())
      return u == dest;
    if (state[u] == State::kVisiting)
      return false;
    if (state[u] == State::kVisited)
      return true;

    state[u] = State::kVisiting;
    for (const int v : graph[u])
      if (!acyclic(graph, v, dest, state))
        return false;
    state[u] = State::kVisited;

    return true;
  }
};




			


enum State { kInit, kVisiting, kVisited }

class Solution {
  public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
    List<Integer>[] graph = new List[n];
    State[] state = new State[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] e : edges)
      graph[e[0]].add(e[1]);

    return acyclic(graph, source, destination, state);
  }

  private boolean acyclic(List<Integer>[] graph, int u, int dest, State[] state) {
    if (graph[u].isEmpty())
      return u == dest;
    if (state[u] == State.kVisiting)
      return false;
    if (state[u] == State.kVisited)
      return true;

    state[u] = State.kVisiting;
    for (final int v : graph[u])
      if (!acyclic(graph, v, dest, state))
        return false;
    state[u] = State.kVisited;

    return true;
  }
}