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.

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

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.