Minimum Number of Vertices to Reach All Nodes
Problem
Given a DAG, return the smallest set of starting vertices from which every node is reachable.
n=6, edges=[[0,1],[0,2],[2,5],[3,4],[4,2]][0,3]def find_smallest_set_of_vertices(n, edges):
seen = [False] * n
for _, v in edges: seen[v] = True
return [i for i in range(n) if not seen[i]]function findSmallestSetOfVertices(n, edges) {
const seen = new Array(n).fill(false);
for (const [, v] of edges) seen[v] = true;
const out = [];
for (let i = 0; i < n; i++) if (!seen[i]) out.push(i);
return out;
}class Solution {
public List findSmallestSetOfVertices(int n, List> edges) {
boolean[] seen = new boolean[n];
for (List e : edges) seen[e.get(1)] = true;
List out = new ArrayList<>();
for (int i = 0; i < n; i++) if (!seen[i]) out.add(i);
return out;
}
} vector findSmallestSetOfVertices(int n, vector>& edges) {
vector seen(n, false);
for (auto& e : edges) seen[e[1]] = true;
vector out;
for (int i = 0; i < n; i++) if (!seen[i]) out.push_back(i);
return out;
} Explanation
This looks like it needs a graph traversal, but there is a beautiful shortcut: in a DAG (directed acyclic graph), the answer is simply every node with in-degree 0 — the nodes that have no incoming edges.
Why must they be included? A node with no incoming edge can never be reached from anywhere else, so the only way to "cover" it is to start there. That makes every such node mandatory.
Why are they enough? Every other node has at least one parent. Follow parents backward and, because the graph has no cycles, you eventually hit a node with no parent — a source. So every node is reachable from some source, and the sources alone cover the whole graph.
The code is therefore tiny: mark every node that appears as a destination v in some edge as seen, then collect the nodes that were never marked. for _, v in edges: seen[v] = True does the marking, and the list comprehension returns the unmarked ones.
Example: with edges [[0,1],[0,2],[2,5],[3,4],[4,2]], the destinations are 1, 2, 5, 4. Only 0 and 3 are never a destination, so the answer is [0, 3].