Description
Given a directed acyclic graph with n vertices and edges, find the smallest set of vertices from which all nodes are reachable.
Examples
Input:
n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]Output:
[0,3]Explanation:
From 0 and 3, all reachable.
Input:
n = 6, edges = [[1]]Output:
[1]Explanation:
Minimal case with a single edge.
Input:
n = 5, edges = [[0,1],[1,2],[3,4]]Output:
[0,3]Explanation:
There are two disconnected components: nodes {0,1,2} and nodes {3,4}. Node 0 can reach nodes 1 and 2, while node 3 can reach node 4. Since nodes 1, 2, and 4 have incoming edges, they don't need to be starting points. Only nodes 0 and 3 have no incoming edges, so they must both be in the minimum set.
Constraints
- •
2 ≤ n ≤ 10⁵