> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# All Paths from Source Lead to Destination

> Tested Python solution for LeetCode 1059 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 1059, [Medium](/catalog/medium). Topics: [Graph](/catalog/topics/graph), [Topological Sort](/catalog/topics/topological-sort), [Depth-First Search](/catalog/topics/depth-first-search), Kosaraju. [View on LeetCode](https://leetcode.com/problems/all-paths-from-source-lead-to-destination/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1059   # by problem number
lcpy gen -s all_paths_from_source_lead_to_destination   # by problem name
```

## Problem

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

### Examples

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

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

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

### Constraints

* 1 \<= n \<= 10^4
* 0 \<= edges.length \<= 10^4
* edges\[i].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.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/all_paths_from_source_lead_to_destination/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/all_paths_from_source_lead_to_destination/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n + e)
    # Space: O(n + e)
    def leads_to_destination(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        graph: list[list[int]] = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
        if graph[destination]:
            return False

        state = [0] * n

        def dfs(i: int) -> bool:
            if state[i]:
                return state[i] == 2
            if not graph[i]:
                return i == destination
            state[i] = 1
            for j in graph[i]:
                if not dfs(j):
                    return False
            state[i] = 2
            return True

        return dfs(source)
```

## Complexity

| Time | Space |
| - | - |
| O(n + e) | O(n + e) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.