# LeetCode 1059. All Paths from Source Lead to Destination

## Description

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`, that is:

• At least one path exists from the `source` node to the `destination` node
• If a path exists from the `source` node to a node with no outgoing edges, then that node is equal to `destination`.
• The number of possible paths from `source` to `destination` is a finite number.

Return `true` if and only if all roads from `source` lead to `destination`.

Example 1:

```Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false
Explanation: It is possible to reach and get stuck on both node 1 and node 2.
```

Example 2:

```Input: n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
Output: false
Explanation: We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.
```

Example 3:

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

Example 4:

```Input: n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2
Output: false
Explanation: All paths from the source node end at the destination node, but there are an infinite number of paths, such as 0-1-2, 0-1-1-2, 0-1-1-1-2, 0-1-1-1-1-2, and so on.
```

Example 5:

```Input: n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1
Output: false
Explanation: There is infinite self-loop at destination node.
```

Constraints:

• `1 <= n <= 104`
• `0 <= edges.length <= 104`
• `edges.length == 2`
• `0 <= ai, bi <= n - 1`
• `0 <= source <= n - 1`
• `0 <= destination <= n - 1`
• The given graph may have self-loops and parallel edges.

## Python Solution

Use depth-first search to see if all paths end with the destination node.

``````class Solution:
def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:

adjacency_list = [set() for i in range(n)]

for edge in edges:

def helper(self, node, destination, adjacency_list, visited):
if node in visited:
return False

if node != destination and not adjacency_list[node]:
return False

if node == destination and len(adjacency_list[node]) > 0:
return False

if node == destination:
return True
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}