Skip to main content

1059 - All Paths from Source Lead to Destination

Difficulty: Medium | Pattern: DFS + Cycle Detection | Company tags: Google, Amazon

Problem Statement​

Given the edges of a directed graph where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi, and two nodes source and destination of this graph, determine whether or not all paths starting from source eventually end at destination.

Conditions that make this false:

  1. There is a path that ends at a node other than destination
  2. There is a path that forms a cycle
  3. destination has outgoing edges (would not be a dead-end for all paths)

Example 1:

Input: n=3, edges=[[0,1],[0,2]], source=0, destination=2
Output: false  (path 0→1 doesn't reach 2)

Example 2:

Input: n=4, edges=[[0,1],[0,3],[1,2],[2,1]], source=0, destination=3
Output: false  (cycle 1↔2)

Example 3:

Input: n=4, edges=[[0,1],[0,2],[1,3],[2,3]], source=0, destination=3
Output: true

Approach: DFS with Coloring — O(V+E)​

Key insight: Three conditions to check:

  1. Destination must have no outgoing edges (otherwise not all paths end there)
  2. No cycles reachable from source
  3. All dead-ends (nodes with no outgoing edges) must be the destination

Use three-color DFS: white (0=unvisited), gray (1=in current path), black (2=fully explored).

Algorithm Flow​

def leadsToDestination(n, edges, source, destination) -> bool:
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
    
    # Destination must have no outgoing edges
    if graph[destination]:
        return False
    
    # 0=unvisited, 1=in-progress, 2=done
    state = [0] * n
    
    def dfs(node):
        if state[node] == 2:
            return True  # already fully explored (no issues)
        if state[node] == 1:
            return False  # cycle detected
        
        state[node] = 1
        
        if not graph[node]:
            # Dead end: must be destination
            state[node] = 2
            return node == destination
        
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        
        state[node] = 2
        return True
    
    return dfs(source)

Dry Run​

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

  • graph[3]=[] ✓ (no outgoing from destination)
  • dfs(0): state[0]=gray
    • dfs(1): state[1]=gray
      • dfs(3): state[3]=gray; no neighbors; 3==destination → state[3]=black; return True
      • state[1]=black; return True
    • dfs(2): state[2]=gray
      • dfs(3): state[3]=black; return True
      • state[2]=black; return True
    • state[0]=black; return True

True ✓

Complexity​

  • Time: O(V + E)
  • Space: O(V + E)

Key Terms​

TermDefinition
DFSDepth-first traversal that explores as far as possible along each branch before backtracking.
Cycle detectionIdentifying a path that revisits a node currently on the recursion stack.
Three-color markingWhite/gray/black states used to distinguish unvisited, in-progress, and fully-explored nodes during DFS.
Dead-end nodeA node with no outgoing edges; every path through it must terminate there.
MemoizationCaching a node's final result (black state) so it is not re-explored on later calls.

FAQ​

Q: Why not just use plain visited/unvisited (two colors) instead of three? A: Two colors can't distinguish "currently on this DFS path" (which signals a cycle) from "already fully verified safe" — you'd re-explore safe subtrees repeatedly or misreport a cross-edge as a cycle.

Q: What if the graph has multiple disconnected components? A: Irrelevant nodes unreachable from source don't matter — DFS only needs to start at source and never has to touch the rest of the graph.

Q: How would this change if edges were undirected? A: The problem becomes about biconnectivity/tree-shape checks instead, since undirected edges make "cycle" and "dead end" mean something different (going back to your parent isn't a real cycle).

Q: Can this be solved with BFS instead of DFS? A: Not naturally — cycle detection via topological ordering (Kahn's algorithm) is possible, but tracking "all paths terminate at destination" is more direct with DFS's recursion stack (gray state).

Q: What is the time/space complexity trade-off vs an iterative approach? A: An iterative DFS with an explicit stack has the same O(V+E) complexity but avoids Python recursion-limit issues on deep or highly connected graphs.

Quick Revision​

  • Problem: verify every path from source ends at destination — no cycles, no wrong dead-ends, destination itself must be a sink.
  • First check: destination must have zero outgoing edges.
  • Use 3-color DFS: 0 = unvisited, 1 = in current path (gray), 2 = fully explored (black).
  • Seeing a gray node again means a cycle → return False immediately.
  • Seeing a black node means it was already proven safe → return True without re-exploring.
  • A node with no outgoing edges is a dead end; it's valid only if it equals destination.
  • A node is safe only if ALL of its neighbors are safe.
  • Time: O(V+E), Space: O(V+E) for recursion stack + state array.
  • This pattern generalizes to "eventual safe states" and cycle-detection-in-directed-graph problems.
  • Course Schedule / Course Schedule III pattern — cycle detection in directed graphs (630 - Course Schedule III)
  • Parallel Courses — topological-order dependency traversal (1136 - Parallel Courses)
  • Find Eventual Safe States (LeetCode 802) — same three-color DFS safety-check pattern (no file in this set)