Problem 20.4 · Graph FundamentalsMedium

Minimum Number of Vertices to Reach All Nodes

What it teaches: In-degree reasoning on a DAG: a node with no incoming edge can only be reached by starting there.

Practise it on judges as “Minimum Number of Vertices to Reach All Nodes”.

The problem

Given a directed acyclic graph with n nodes, return the smallest set of nodes from which every node is reachable, in ascending order (the answer is unique).

Example 1

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

Constraints

2 ≤ n ≤ 10⁵
The graph is acyclic

Pattern clues in the wording

→ DAG
→ Smallest set of starting points

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 6 edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]	[0,3]
2	n = 5 edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]	[0,2,3]

From slow to fast

Approaches

1. Nodes with in-degree 0 · O(V + E)

Nodes with in-degree 0

Time O(V + E) Space O(V)

Mark every edge's target. The unmarked nodes must be in the set, and they are enough because in a DAG every node traces back to a source.

Approach 1

import java.util.*;

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        boolean[] hasIncoming = new boolean[n];
        for (List<Integer> e : edges) hasIncoming[e.get(1)] = true;
        List<Integer> out = new ArrayList<>();
        for (int v = 0; v < n; v++) if (!hasIncoming[v]) out.add(v);
        return out;
    }
}

Verdict: No traversal needed.

Before you submit

Edge cases and common mistakes

Test these inputs

A chain (one source)
No edges (every node is a source)

Mistakes people make

Running BFS from every node (O(V × (V + E))).

Interview

Follow-up questions

What if the graph could have cycles?

Command Palette

The problem

Approaches

Nodes with in-degree 0

Edge cases and common mistakes

Follow-up questions