All Paths from Source Lead to Destination

medium graph dfs cycle detection

Problem

Given a directed graph with n nodes and an edge list, plus a source and a destination, return true if and only if every possible path that starts at source ends at destination. This requires three conditions: no path can reach a dead-end node (a node with no outgoing edges) that is not the destination, the destination itself must have no outgoing edges, and there must be no cycle reachable from the source.

Inputn = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3

Outputfalse

From 0 we can go 0→1→2→1→2… — a cycle between 1 and 2 — so not every path reaches 3.

n (node count)

edges (e.g. 0-1, 0-3, 1-2, 2-1)

source

destination

def leads_to_destination(n, edges, source, destination):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
    # color: 0 = unvisited, 1 = on current path, 2 = done (safe)
    color = [0] * n

    def dfs(u):
        if g[u] == []:
            return u == destination
        if color[u] == 1:
            return False          # back edge -> cycle
        if color[u] == 2:
            return True           # already proven safe
        color[u] = 1
        for v in g[u]:
            if not dfs(v):
                return False
        color[u] = 2
        return True

    return dfs(source)

function leadsToDestination(n, edges, source, destination) {
  const g = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) g[u].push(v);
  // color: 0 = unvisited, 1 = on current path, 2 = done (safe)
  const color = new Array(n).fill(0);

  function dfs(u) {
    if (g[u].length === 0) return u === destination;
    if (color[u] === 1) return false;   // back edge -> cycle
    if (color[u] === 2) return true;     // already proven safe
    color[u] = 1;
    for (const v of g[u]) {
      if (!dfs(v)) return false;
    }
    color[u] = 2;
    return true;
  }

  return dfs(source);
}

class Solution {
    int[] color;
    List<List<Integer>> g;
    int destination;

    public boolean leadsToDestination(int n, int[][] edges, int source, int dest) {
        g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) g.get(e[0]).add(e[1]);
        color = new int[n];      // 0 unvisited, 1 on path, 2 safe
        destination = dest;
        return dfs(source);
    }

    boolean dfs(int u) {
        if (g.get(u).isEmpty()) return u == destination;
        if (color[u] == 1) return false;   // cycle
        if (color[u] == 2) return true;
        color[u] = 1;
        for (int v : g.get(u)) if (!dfs(v)) return false;
        color[u] = 2;
        return true;
    }
}

class Solution {
    vector<vector<int>> g;
    vector<int> color;   // 0 unvisited, 1 on path, 2 safe
    int dest;
public:
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        g.assign(n, {});
        for (auto& e : edges) g[e[0]].push_back(e[1]);
        color.assign(n, 0);
        dest = destination;
        return dfs(source);
    }
    bool dfs(int u) {
        if (g[u].empty()) return u == dest;
        if (color[u] == 1) return false;   // cycle
        if (color[u] == 2) return true;
        color[u] = 1;
        for (int v : g[u]) if (!dfs(v)) return false;
        color[u] = 2;
        return true;
    }
};

Explanation

We want to be sure that every walk from source ends at destination. The trick is a DFS that paints each node one of three colors as it explores, which lets us catch both dead-ends and cycles in a single pass.

The colors mean: 0 = not visited, 1 = currently on the DFS path, and 2 = fully explored and proven safe. When DFS reaches a node, it returns false if that node is a dead-end that is not the destination, or if it is colored 1 (we came back to a node already on our path, which means a cycle).

Otherwise we mark the node 1, recurse into all its neighbours, and only if every neighbour returns true do we mark it 2 (safe) and return true. The color 2 lets us skip re-exploring nodes we already proved safe.

Example: n=4, edges=[[0,1],[0,3],[1,2],[2,1]]. From 0 we go to 1 → 2 → 1, but 1 is still color 1 (on the path), so a cycle is detected and the answer is false.

Time: O(n + e) Space: O(n + e)