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
35
36
37
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) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
    }

    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
34
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[] states = new State[n];
    Arrays.setAll(graph, i -> new ArrayList<>());

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
    }

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

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

    return true;
  }
}