Leetcode

All Paths from Source Lead to Destination

May 26, 2022 by aAshish

  • Time:O(|V| + |E|), where |V| = n and |E| = |\texttt{edges}|
  • Space:O(|V| + |E|), where |V| = n and |E| = |\texttt{edges}|

C++

 
enum class State { INIT, VISITING, VISITED };

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 auto& 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::VISITING)
      return false;
    if (state[u] == State::VISITED)
      return true;

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

    return true;
  }
};

JAVA

 
enum State { INIT, VISITING, VISITED }

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.VISITING)
      return false;
    if (state[u] == State.VISITED)
      return true;

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

    return true;
  }
}