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

# Minimum Number of Vertices to Reach All Nodes

> Tested Python solution for LeetCode 1557 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 1557, [Medium](/catalog/medium). Topics: [Graph Theory](/catalog/topics/graph-theory), Directed Acyclic Graph. [View on LeetCode](https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/).

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

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

## Problem

Given a **directed acyclic graph**, with `n` vertices numbered from `0` to `n - 1`, and an array `edges` where `edges[i] = [from_i, to_i]` represents a directed edge from node `from_i` to node `to_i`.

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/07/07/untitled22.png)

```
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output: [0,3]
```

**Explanation:** It's not possible to reach all the nodes from a single vertex. From 0 we can reach \[0,1,2,5]. From 3 we can reach \[3,4,2,5]. So we output \[0,3].

![Example 2](https://assets.leetcode.com/uploads/2020/07/07/untitled.png)

```
Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output: [0,2,3]
```

**Explanation:** Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.

### Constraints

* `2 <= n <= 10^5`
* `1 <= edges.length <= min(10^5, n * (n - 1) / 2)`
* `edges[i].length == 2`
* `0 <= from_i, to_i < n`
* All pairs (from\_i, to\_i) are distinct.

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n + e)
    # Space: O(n)
    def find_smallest_set_of_vertices(self, n: int, edges: list[list[int]]) -> list[int]:
        has_incoming = [False] * n
        for _from, to in edges:
            has_incoming[to] = True
        return [node for node in range(n) if not has_incoming[node]]
```

## Complexity

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

## Tags

[NeetCode All](/catalog/neetcode).


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