Problem Description

You are given a directed graph with n nodes (labeled from 0 to n-1) represented by an edge list where edges[i] = [ai, bi] means there is a directed edge from node ai to node bi. You are also given two specific nodes: source and destination.

Your task is to determine if all paths starting from source eventually lead to destination.

For this to be true, three conditions must be satisfied:

1. At least one path exists from source to destination
2. Any terminal node must be the destination: If you can reach a node that has no outgoing edges (a dead end), that node must be destination
3. No infinite loops: The number of possible paths from source to destination must be finite (meaning there are no cycles that can be reached from source)

Return true if all paths from source lead to destination, otherwise return false.

Example scenarios:

• If there's a path from source that reaches a dead-end node other than destination, return false
• If there's a cycle reachable from source, return false (as this creates infinite paths)
• If all paths from source eventually reach destination and nowhere else, return true

Intuition

To check if all paths from source lead to destination, we need to explore every possible path starting from source and verify that each one satisfies our conditions.

The key insight is that we can use depth-first search (DFS) to traverse all paths from the source. During our traversal, we need to handle three critical scenarios:

1. Reaching the destination: When we reach the destination node, we need to verify it's a valid terminal point. The destination should have no outgoing edges (it should be a dead end), otherwise paths could continue beyond it.

2. Detecting cycles: If we encounter a node we're currently visiting in our DFS path (a node in our current recursion stack), we've found a cycle. This violates the finite paths requirement, so we should return false.

3. Finding other dead ends: If we reach a node with no outgoing edges that isn't the destination, we've found a path that doesn't lead to our target, so we should return false.

The algorithm naturally emerges from these observations:

• We maintain a visited set to track nodes in our current DFS path (to detect cycles)
• For each node, we recursively check all its neighbors
• We only return true if all recursive calls from a node return true
• We use memoization (@cache) to avoid recomputing results for nodes we've already fully explored

The beauty of this approach is that DFS naturally explores all possible paths, and by checking our three conditions at each step, we can determine if every path from source eventually leads to destination.

Learn more about Graph and Topological Sort patterns.

Solution Approach

The solution implements a DFS-based approach with memoization to efficiently check all paths from the source node.

Data Structures Used:

• g: A dictionary (defaultdict) to store the adjacency list representation of the graph
• vis: A set to track nodes currently being visited in the DFS path (for cycle detection)
• @cache: Decorator for memoization to avoid recomputing results for already processed nodes

Implementation Steps:

1. Build the Graph:

   g = defaultdict(list)
   for a, b in edges:
       g[a].append(b)

   We convert the edge list into an adjacency list for efficient traversal.

2. DFS Function with Memoization:

   @cache
   def dfs(i):

   The dfs function recursively explores all paths from node i. The @cache decorator ensures we don't recompute results for nodes we've already fully explored.

3. Base Cases:

   • Reached destination:

     if i == destination:
         return not g[i]

     If we reach the destination, we return True only if it has no outgoing edges (it's a terminal node).

   • Cycle detection or dead end:

     if i in vis or not g[i]:
         return False

     If the node is already in our current path (i in vis), we've found a cycle. If the node has no outgoing edges (not g[i]) and it's not the destination, it's an invalid dead end.

4. Recursive Exploration:

   vis.add(i)
   for j in g[i]:
       if not dfs(j):
           return False
   return True

   • Add the current node to the visited set
   • Recursively check all neighbors
   • If any neighbor path returns False, the current path is invalid
   • If all neighbor paths are valid, return True

5. Main Execution:

   vis = set()
   return dfs(source)

   Initialize the visited set and start DFS from the source node.

The algorithm correctly handles all three requirements: it finds paths to destination, detects cycles (infinite paths), and identifies invalid terminal nodes. The time complexity is O(V + E) where V is the number of vertices and E is the number of edges, as we visit each node and edge at most once due to memoization.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Graph:

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

This creates the following graph:

    0
   / \
  1   2
   \ /
    3

Step-by-step DFS execution:

1. Start: dfs(0)

   • Node 0 is not the destination
   • Node 0 is not in vis and has outgoing edges [1, 2]
   • Add 0 to vis: vis = {0}
   • Need to check dfs(1) and dfs(2)

2. First branch: dfs(1)

   • Node 1 is not the destination
   • Node 1 is not in vis and has outgoing edges [3]
   • Add 1 to vis: vis = {0, 1}
   • Need to check dfs(3)

3. Reach destination: dfs(3)

   • Node 3 is the destination
   • Check if node 3 has outgoing edges: g[3] = [] (empty)
   • Since destination has no outgoing edges, return True
   • Remove 1 from vis (backtrack): vis = {0}

4. Second branch: dfs(2)

   • Node 2 is not the destination
   • Node 2 is not in vis and has outgoing edges [3]
   • Add 2 to vis: vis = {0, 2}
   • Need to check dfs(3)

5. Reach destination again: dfs(3)

   • Due to @cache, we don't recompute - immediately return True
   • Remove 2 from vis (backtrack): vis = {0}

6. Final result:

   • Both paths from node 0 (0→1→3 and 0→2→3) lead to destination
   • Destination has no outgoing edges (valid terminal)
   • No cycles detected
   • Return True

Counter-example with a cycle:

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

This creates:

    0 → 1 ⟷ 2
        ↓
        3

When we reach node 2, it points back to node 1. If we follow 2→1, node 1 is already in vis, indicating a cycle. The function would return False because infinite paths exist (we can loop 1→2→1→2... forever).

Solution Implementation

Time and Space Complexity

Time Complexity: O(V + E) where V is the number of vertices (n) and E is the number of edges.

The algorithm performs a depth-first search (DFS) traversal of the graph. Due to the @cache decorator and the vis set working together:

• Each node is visited at most once during the DFS traversal (the vis set ensures we don't revisit nodes in the current path, preventing infinite loops in cycles)
• The @cache decorator memoizes results, so if we encounter the same node through different paths, we return the cached result in O(1) time
• Building the adjacency list takes O(E) time as we iterate through all edges once
• The DFS explores each edge at most once, contributing O(E) to the traversal
• Each node is processed at most once, contributing O(V) to the traversal

Space Complexity: O(V + E)

The space usage comes from several components:

• The adjacency list g stores all edges, requiring O(E) space
• The vis set can contain at most O(V) nodes in the worst case (when traversing a long path)
• The @cache decorator stores memoized results for at most O(V) different nodes
• The recursive call stack depth can be at most O(V) in the worst case (a linear chain of nodes)
• Overall, the space complexity is O(V + E) dominated by the adjacency list and the combined space of memoization, visited set, and recursion stack

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Incorrect Cycle Detection with Memoization

The Problem: The provided solution has a critical bug in how it handles the visited set with memoization. The visited set is used to track nodes in the current DFS path for cycle detection, but it's never cleared after exploring a path. When combined with the @cache decorator, this creates incorrect behavior:

1. Once a node is added to visited, it remains there permanently
2. The cached result for a node might be based on an incorrect cycle detection from a previous path
3. Valid paths might be incorrectly marked as having cycles

Example Scenario: Consider a graph where:

• Path 1: source → A → B → destination
• Path 2: source → C → B → destination

When exploring Path 1, node B is added to visited. Later, when exploring Path 2 through node C, if we try to visit B again, it will incorrectly appear as a cycle because B is still in visited from the previous path exploration.

The Solution: Remove nodes from the visited set after exploring them (backtracking), ensuring that visited only contains nodes in the current DFS path:

@cache
def dfs(current_node: int) -> bool:
    # Base case: reached destination
    if current_node == destination:
        return len(graph[current_node]) == 0
  
    # Check for cycle or dead-end
    if current_node in visited or len(graph[current_node]) == 0:
        return False
  
    # Mark current node as visited
    visited.add(current_node)
  
    # Explore all neighbors
    result = True
    for neighbor in graph[current_node]:
        if not dfs(neighbor):
            result = False
            break
  
    # CRITICAL: Remove from visited set after exploration (backtrack)
    visited.remove(current_node)
  
    return result

Alternative Approach - Using Node States: A more robust approach is to use three states for nodes instead of a simple visited set:

def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
    graph = defaultdict(list)
    for from_node, to_node in edges:
        graph[from_node].append(to_node)
  
    # States: 0 = unvisited, 1 = visiting (in current path), 2 = visited (fully processed)
    state = [0] * n
  
    def dfs(node: int) -> bool:
        if state[node] == 1:  # Cycle detected
            return False
        if state[node] == 2:  # Already processed
            return True
      
        if node == destination:
            return len(graph[node]) == 0
      
        if len(graph[node]) == 0:  # Dead end that's not destination
            return False
      
        state[node] = 1  # Mark as visiting
      
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
      
        state[node] = 2  # Mark as visited
        return True
  
    return dfs(source)

This three-state approach clearly distinguishes between:

• Nodes currently being explored (state 1) - for cycle detection
• Nodes fully processed (state 2) - for memoization
• Unvisited nodes (state 0) - yet to be explored

This prevents the confusion between cycle detection and memoization that occurs in the original solution.