Skip to content

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<vector<int>>& edges, int source,
                          int destination) {
    vector<vector<int>> graph(n);
    vector<State> states(n);

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

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

 private:
  bool acyclic(const vector<vector<int>>& graph, int u, int dest,
               vector<State>& 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<Integer>[] 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<Integer>[] 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;
  }
}