1059. All Paths from Source Lead to Destination


Problem Description

The problem provides us with a directed graph, defined by pairs of nodes that represent edges. We're asked to determine if every path that starts at a node called source will invariably end at another node called destination. To be more specific, the problem stipulates three conditions that must be met for us to return true:

  1. There must be at least one path from the source to the destination.
  2. If any path leads to a node that doesn't have outgoing edges (a dead end), then that node must be the destination.
  3. The total number of paths from source to destination has to be finite, meaning there cannot be any infinite loops along the way.

If all these conditions are met, we can confidently say that all roads from source lead to the destination.

Intuition

To find a solution, we need to do a traversal of the graph starting from the source node. Depth-first search (DFS) is a natural fit for exploring all paths in the graph efficiently. The following considerations are vital in our approach:

  1. Termination at Destination: If during our DFS we reach the destination without any outgoing edges, we're on the right track.
  2. Detecting Dead Ends: If we encounter a node that is not the destination and has no outgoing edges, we've found a dead end, and our condition breaks.
  3. Handling Cycles: We need to detect cycles to ensure there's a finite number of paths. If we revisit a node during the DFS, we've encountered a cycle, and thus not all paths lead to the destination.
  4. Graph Representation: The graph is represented as an adjacency list, allowing for easy iteration over the neighbors of each node.
  5. Memoization: To avoid unnecessary re-computation, results of traversals are cached.

With these in mind, we perform the DFS recursively starting from the source, marking visited nodes to detect cycles, and checking if every path either reaches destination without further moves or continues only to other nodes that also satisfy these criteria.

The code provided is a neat implementation of these ideas using a recursive DFS with memoization (@cache decorator) and a set (vis) to keep track of visited nodes to avoid cycles. If any path ends at a node that is not the destination or leads back to an already visited node, the function returns False; otherwise, it continues until all paths are verified to meet the criteria, at which point it returns True.

Learn more about Depth-First Search and Graph patterns.

Solution Approach

The solution uses a depth-first search (DFS) approach, which is a common technique for exploring all possible paths in a graph. Here is a step-by-step breakdown of how the implementation works:

  1. Adjacency List Creation: The list g is a defaultdict from Python's collections module, which maps each node to a list of its adjacent nodes (those that can be reached by a direct edge from it).

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

    This data structure is efficient for our graph representation, as it allows for quick additions of edges and retrieval of neighbors.

  2. Deep First Search: The dfs function is a recursive function that is used to perform DFS on the graph. It takes a node index i as an argument and returns True if all paths from that node lead to the destination while fulfilling the mentioned criteria.

    1@cache
    2def dfs(i):
    3    # Base cases for recursion
    4    if i == destination:
    5        return not g[i] # Must be no outgoing edges from destination
    6    if i in vis or not g[i]:
    7        return False # Return False if we hit a visited node (cycle) or dead-end
    8    vis.add(i) # Mark current node as visited
    9    for j in g[i]:
    10        if not dfs(j):
    11            return False # If any path doesn't lead to the destination, return False
    12    return True # All paths from node i lead to the destination

    The dfs function includes several critical checks:

    • If the current node (i) is the destination and has no outgoing edges, return True.
    • If the current node is revisited (i in vis) or it is a dead-end (no outgoing edges and not the destination), return False.
    • For every adjacent node j of i, call dfs(j) recursively. If dfs(j) returns False, then not all paths from i lead to the destination, and the function returns False.
    • If all adjacent nodes lead to paths that satisfy the conditions, return True.
  3. Caching and Visited Set: The solution employs caching (@cache decorator) to store the results of DFS calls to avoid repeated computation on the same node. Additionally, a set vis is used to track visited nodes during the DFS to detect cycles.

    1vis = set()
  4. DFS Initialization: The DFS starts from the source node.

    1return dfs(source)

    The result of this initial call to dfs determines whether all roads from source lead to destination.

By combining these steps, the solution effectively traverses the graph to ensure every path from source leads to destination and there are no infinite paths, thus solving the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's use a small example to illustrate how the solution approach works. Consider a graph represented by the following set of directed edges, where the source node is 0 and the destination node is 2:

10 -> 1
21 -> 2
30 -> 2

Following the steps listed in the solution approach:

  1. Adjacency List Creation: We first create an adjacency list from the given set of edges. Here, the graph g will map each node to its list of adjacent nodes:

    1g = defaultdict(list, {0: [1, 2], 1: [2], 2: []})

    The defaultdict allows us to append nodes easily, and we can see that node 0 has edges to nodes 1 and 2, node 1 to node 2, and node 2 has no outgoing edges.

  2. Deep First Search: We begin our DFS by calling dfs(0):

    1@cache
    2def dfs(i):
    3    if i == destination:
    4        return not g[i]
    5    if i in vis or not g[i]:
    6        return False
    7    vis.add(i)
    8    for j in g[i]:
    9        if not dfs(j):
    10            return False
    11    return True

    During the initial call dfs(0), we find that 0 is not the destination and has outgoing edges. We add 0 to vis and explore its adjacent nodes: 1 and 2.

    • For node 1, we call dfs(1). Node 1 is not the destination, so we check its adjacency list and call dfs(2) on its sole adjacent node. Since 2 is the destination and has no outgoing edges, dfs(2) returns True.
    • After exploring node 1, we continue with node 2. Since it's the destination with no outgoing edges, dfs(2) instantly returns True.

    Because both dfs(1) and dfs(2) return True, dfs(0) also returns True.

  3. Caching and Visited Set: The @cache decorator ensures that the result of dfs(2) is stored and reused when dfs(2) is called again, saving time. The vis set prevents us from re-visiting the same node, which also helps in detecting cycles.

    1vis = set()
  4. DFS Initialization: The DFS starts with dfs(source):

    1return dfs(0)

    Since dfs(0) returns True, it means that every path from the source (node 0) leads to the destination (node 2), and thus the function as a whole returns True.

By traversing this simple graph, we have used the provided DFS algorithm to confirm that all paths from source lead to destination, with no dead ends or cycles, satisfying all three conditions for the problem.

Solution Implementation

1from collections import defaultdict
2from functools import lru_cache
3
4class Solution:
5    def leadsToDestination(self, n: int, edges: list, source: int, destination: int) -> bool:
6        # Decorator to cache results of the DFS function
7        @lru_cache(maxsize=None)
8        def dfs(node):
9            # If we reach the destination, return True if there are no outgoing edges (leaf node)
10            if node == destination:
11                return len(graph[node]) == 0
12          
13            # If we've visited this node before or it has no outgoing edges (meaning it's not a destination),
14            # we're in a cycle or a dead end, so we return False.
15            if node in visited or not graph[node]:
16                return False
17          
18            # Mark this node as visited
19            visited.add(node)
20          
21            # Iterate through all the edges of the current node
22            for adjacent in graph[node]:
23                # If any of the deeper calls return False, we propagate False up the stack.
24                if not dfs(adjacent):
25                    return False
26          
27            # All paths from the current node lead to the destination, we can clean up the visited set and return True.
28            visited.remove(node)
29            return True
30
31        # Initialize a default dictionary to store a list of nodes for each key
32        graph = defaultdict(list)
33      
34        # Populate the graph with the edges
35        for start, end in edges:
36            graph[start].append(end)
37      
38        # Use a set to track visited nodes to detect cycles
39        visited = set()
40      
41        # Start DFS from the source node
42        return dfs(source)
43
1class Solution {
2    private List<Integer>[] graph; // adjacency list to represent the graph
3    private int[] state; // state array to mark nodes as not visited(0), visited(1), or not leading to destination(-1)
4    private boolean[] visited; // visited array to keep track of the visited nodes in the current path
5    private int destination; // the target destination node
6
7    // method to determine if all paths starting from the source lead to the destination
8    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
9        // initialize the visited array, graph, destination, and state arrays
10        visited = new boolean[n];
11        graph = new List[n];
12        this.destination = destination;
13        state = new int[n];
14        // fill the graph adjacency list
15        Arrays.setAll(graph, x -> new ArrayList<>());
16        for (int[] edge : edges) {
17            graph[edge[0]].add(edge[1]);
18        }
19        // start DFS from the source node
20        return dfs(source);
21    }
22
23    // helper method for DFS traversal
24    private boolean dfs(int node) {
25        // if the current node is the destination, check if there are no outgoing edges (leaf node)
26        if (node == destination) {
27            return graph[node].isEmpty();
28        }
29        // if the current node's state is already computed, return true if it's 1
30        if (state[node] != 0) {
31            return state[node] == 1;
32        }
33        // if the current node is visited or has no outgoing edges, it does not lead to destination
34        if (visited[node] || graph[node].isEmpty()) {
35            return false;
36        }
37        // mark the current node as visited
38        visited[node] = true;
39        // traverse all the adjacent nodes
40        for (int nextNode : graph[node]) {
41            // if any adjacent does not lead to the destination, mark current node's state as -1 and return false
42            if (!dfs(nextNode)) {
43                state[node] = -1;
44                return false;
45            }
46        }
47        // after visiting all adjacent nodes and they lead to destination, set current node's state to 1
48        state[node] = 1;
49        return true;
50    }
51}
52
1class Solution {
2public:
3    // Method to determine if there is a path from the `source` node to the `destination` node
4    // such that all paths from `source` eventually lead to `destination` and no nodes are visited more than once.
5    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
6        // Visited nodes tracker to avoid visiting a node more than once in a path
7        vector<bool> visited(n, false);
8        // Graph represented as adjacency list
9        vector<vector<int>> graph(n);
10        // Flag array to keep track of nodes that have been processed
11        // 0: unvisited, 1: path leads to destination, -1: path does not lead to destination
12        vector<int> flags(n, 0);
13
14        // Build the graph from the edges
15        for (const auto& edge : edges) {
16            graph[edge[0]].push_back(edge[1]);
17        }
18      
19        // Recursive Depth First Search (DFS) lambda function to traverse the graph
20        function<bool(int)> dfs = [&](int node) {
21            // If reached destination, the path is valid if there are no outgoing edges from the destination
22            if (node == destination) {
23                return graph[node].empty();
24            }
25            // If the current node has been processed, return its status
26            if (flags[node] != 0) {
27                return flags[node] == 1;
28            }
29            // If the current node is visited in the current path or no outgoing edges, it cannot lead to the destination
30            if (visited[node] || graph[node].empty()) {
31                return false;
32            }
33          
34            // Mark the node as visited
35            visited[node] = true;
36            // Explore all adjacent nodes
37            for (int adjacentNode : graph[node]) {
38                // If any adjacent node does not lead to destination, set path status to false (-1) and return false
39                if (!dfs(adjacentNode)) {
40                    flags[node] = -1;
41                    return false;
42                }
43            }
44            // Mark this node's path status to true (1) as all its outgoing paths lead to destination
45            flags[node] = 1;
46            // Reset visited for the current node to allow other paths to visit it
47            visited[node] = false;
48            // Returning true as this node leads to the destination
49            return true;
50        };
51      
52        // Start the DFS traversal from the source node to determine if it leads to destination
53        return dfs(source);
54    }
55};
56
1// Define the Node type for clarity
2type Node = number;
3
4// Initialize an adjacency list for the graph
5const graph: Node[][] = [];
6// Initialize visited nodes tracker to avoid visiting a node more than once in a path
7const visited: boolean[] = [];
8// Initialize flags array to keep track of nodes that have been processed
9// 0: unvisited, 1: path leads to destination, -1: path does not lead to destination
10const flags: number[] = [];
11
12// Method to determine if there is a path from the `source` node to the `destination` node
13// such that all paths from `source` eventually lead to `destination` and no nodes are visited more than once.
14function leadsToDestination(n: number, edges: number[][], source: Node, destination: Node): boolean {
15
16  // Clear previous graph data
17  graph.length = 0;
18  // Build the graph from the edges
19  for (let i = 0; i < n; i++) {
20    graph.push([]);
21  }
22  edges.forEach(edge => {
23    graph[edge[0]].push(edge[1]);
24  });
25
26  // Reset visited and flags for each run
27  visited.fill(false, 0, n);
28  flags.fill(0, 0, n);
29
30  // Recursive Depth-First Search (DFS) to traverse the graph
31  function dfs(node: Node): boolean {
32    // If reached destination, the path is valid if there are no outgoing edges from the destination
33    if (node === destination) {
34      return graph[node].length === 0;
35    }
36    // If the current node has been processed, return its status
37    if (flags[node] !== 0) {
38      return flags[node] === 1;
39    }
40    // If the current node is visited in the current path or no outgoing edges, it cannot lead to the destination
41    if (visited[node] || graph[node].length === 0) {
42      return false;
43    }
44
45    // Mark the node as visited
46    visited[node] = true;
47    // Explore all adjacent nodes
48    for (const adjacentNode of graph[node]) {
49      // If any adjacent node does not lead to destination, set path status to false (-1) and return false
50      if (!dfs(adjacentNode)) {
51        flags[node] = -1;
52        visited[node] = false;
53        return false;
54      }
55    }
56    // Mark this node's path status to true (1) as all its outgoing paths lead to destination
57    flags[node] = 1;
58    // Reset visited state for the current node to allow other paths to visit it
59    visited[node] = false;
60    // Return true as this node leads to the destination
61    return true;
62  }
63
64  // Start the DFS traversal from the source node to determine if it leads to the destination
65  return dfs(source);
66}
67
68// We must initialize the graph, visited, and flags arrays with the appropriate size 'n' before we can call leadsToDestination.
69// This would typically be done at the time of execution, after receiving inputs for 'n', 'edges', 'source', and 'destination'.
70

Time and Space Complexity

The given Python code defines a method leadsToDestination which determines whether all paths starting from source lead to destination without any cycles, given the number of nodes n, the directed edges of a graph in the list edges, and the two integers source and destination. The method uses Depth-First Search (DFS) with memoization to check paths from source. Let's break down its time and space complexity:

Time Complexity:

  • Creation of the graph: The graph (g) is built using a default dictionary with adjacency lists. The time to insert all the edges is O(E), where E is the number of edges.
  • DFS traversal: Each node is visited at most once due to memoization provided by @cache which caches the result of the function calls with given arguments. Thus, the DFS traversal will touch each node only once, making it O(V) for visiting V vertices.
  • Checking each adjacency list: For every node, we explore each out-edge once. Since each edge is considered only once in the DFS, the time for this is proportional to the number of edges, which is O(E).

Therefore, the total time complexity is the sum of the graph creation plus the DFS traversal across all edges, resulting in O(V + E).

Space Complexity:

  • Recursion stack: In the worst-case scenario, the recursion can go as deep as the longest path in the graph without visiting the same node twice due to the checks for already visited nodes, which is O(V).
  • Visited set and memoization cache: The visited set vis and the cache used for memoization both store information that could potentially include all the nodes in the graph, thus requiring O(V) space.
  • Graph representation: The graph itself takes O(V + E) space, as each node and edge is stored once.

Given the above components, the total space complexity is determined by the largest term, which is the graph representation combined with the potential space occupied by the recursion stack and the memoization cache, leading to O(V + E).

In conclusion, the code has a time complexity of O(V + E) and a space complexity of O(V + E).

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


Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄