# 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`.

## 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.

๐ช
Level Up Your
Algo Skills

### 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
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.

## Python Solution

``````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
20
21            # Iterate through all the edges of the current node
23                # If any of the deeper calls return False, we propagate False up the stack.
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``````

## Java Solution

``````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) {
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``````

## C++ Solution

``````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
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``````

## Typescript Solution

``````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
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)`.

๐
Become an
Algo Monster

Got a question?ย Ask the Teaching 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.

โ
โTA ๐จโ๐ซ