Problem statement

Given a directed acyclic graph with n nodes labelled 0 through n - 1 and an edge list where edges[i] = [from, to], find the smallest set of vertices from which every node in the graph is reachable.

Return that set in ascending order; it is unique.

Example 1

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

Example 2

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

Example 3

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

Constraints

• 1 <= n <= 40
• 0 <= edges.length <= 60
• The graph is a DAG with no duplicate edges.

Hints for Minimum Number of Vertices to Reach All Nodes

1. Hint 1

   A node with an incoming edge is reachable from somewhere else, so it never has to be in the set.

2. Hint 2

   A node with no incoming edge cannot be reached at all, so it must be in the set.

3. Hint 3

   Since the graph is acyclic, those source nodes alone reach everything — just count in-degrees.

How to solve Minimum Number of Vertices to Reach All Nodes

In a DAG a node with an incoming edge is reachable from its predecessor, and a node with none can only be reached by starting there — so the answer is exactly the set of in-degree-zero nodes.

Approach

1. Mark every edge target as having an incoming edge.
2. Return the nodes not marked, in ascending order.

Why it works

Every node is reachable from some source (follow predecessors backward; acyclicity guarantees the walk ends at an in-degree-zero node), and no source is reachable from any other node.

Complexity

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

Pitfalls

• This relies on acyclicity; with cycles the minimum set is a harder problem.

Reference solution

Python

def findSmallestSetOfVertices(n: int, edges):
    has_incoming = [False] * n
    for _, to in edges:
        has_incoming[to] = True
    return [i for i in range(n) if not has_incoming[i]]

Java

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

C++

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    vector<bool> hasIncoming(n, false);
    for (const auto& e : edges) hasIncoming[e[1]] = true;
    vector<int> out;
    for (int i = 0; i < n; i++) {
        if (!hasIncoming[i]) out.push_back(i);
    }
    return out;
}

JavaScript

var findSmallestSetOfVertices = function(n, edges) {
    const hasIncoming = [];
    for (let i = 0; i < n; i++) hasIncoming.push(false);
    for (let i = 0; i < edges.length; i++) hasIncoming[edges[i][1]] = true;
    const out = [];
    for (let i = 0; i < n; i++) {
        if (!hasIncoming[i]) out.push(i);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More graph problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Minimum Time to Reach Destination in Directed Graph Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium