Choose Starting Vertices for a DAG
Company: Anduril
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A directed acyclic graph has vertices `0` through `n-1`. Each pair in `edges` describes a directed edge from its first vertex to its second. Return a smallest set of starting vertices from which every vertex is reachable. The set is unique, and its elements may be listed in any order.
```cpp
class Solution {
public:
vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges);
};
```
### Examples
**Example 1:**
```text
n = 4, edges = [[0,1],[2,1],[1,3]]
Output: [0,2]
Explanation: Vertices 0 and 2 have no incoming edges, and together reach all four vertices.
```
**Example 2:**
```text
n = 3, edges = [[1,0],[0,2]]
Output: [1]
Explanation: The path 1 -> 0 -> 2 reaches every vertex.
```
### Constraints
- `2 <= n <= 10^5`.
- `1 <= edges.length <= min(10^5, n * (n-1) / 2)`.
- Each edge has two endpoints in `[0,n-1]`.
- Directed endpoint pairs are distinct; the graph is acyclic.
### Clarifying Questions
A starting vertex reaches itself by a path of length zero. The required vertex set is unique, but the returned vector has no prescribed ordering.
```hint Inspect the structure
What must the returned starts collectively reach, and how would you justify that fewer starts cannot suffice?
```
### What a Strong Answer Covers
- Establish reachability of every vertex from the returned starting set.
- Prove that no smaller set can work, without imposing an order on its elements.
### Follow-up Questions
What changes if directed cycles are permitted and strongly connected components are condensed first?
Overview: Choose Starting Vertices for a DAG. A directed acyclic graph has vertices 0 through n-1. Each pair in edges describes a directed edge from its first vertex to its second. Return a smallest set of starting vertices from which every vertex is reachable.