# LeetCode 1059: All Paths from Source Lead to Destination

## Problem Restatement

We are given a directed graph with `n` nodes, a source node, and a destination node.

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

This requires:
1. Every path from `source` eventually reaches `destination`.
2. `destination` has no outgoing edges (it is a terminal node on all paths).

The official constraints state that `1 <= n <= 10^4` and `0 <= edges.length <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `n`, `edges`, `source`, `destination` |
| Output | `true` if all paths from source lead to destination |

Function shape:

```python
def leadsToDestination(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    ...
```

## Key Insight

DFS from source. Use three states for each node:

- `0`: unvisited.
- `1`: currently in the DFS stack (cycle detection).
- `2`: fully processed (all paths from here lead to destination).

If we visit a node in state `1`, we have a cycle → return `False`.

If we reach a node with no outgoing edges, it must be the destination → otherwise `False`.

## Edge Cases

- Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
- Return the failure value when the destination is unreachable.
- Check grid or graph boundaries before reading neighbors.

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
from collections import defaultdict

class Solution:
    def leadsToDestination(self, n: int, edges: list[list[int]], source: int, destination: int) -> bool:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)

        state = [0] * n

        def dfs(node):
            if state[node] != 0:
                return state[node] == 2
            if not graph[node]:
                return node == destination

            state[node] = 1
            for nb in graph[node]:
                if not dfs(nb):
                    return False
            state[node] = 2
            return True

        return dfs(source)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.leadsToDestination(3, [[0,1],[0,2]], 0, 2) == False
    assert s.leadsToDestination(4, [[0,1],[0,3],[1,2],[2,1]], 0, 3) == False
    assert s.leadsToDestination(4, [[0,1],[0,2],[1,3],[2,3]], 0, 3) == True

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Path to non-destination leaf | `False` | Node 2 is a leaf but not destination |
| Cycle | `False` | Nodes 1 and 2 form a cycle |
| All paths to node 3 | `True` | Both paths lead to destination |