Minimum Number of Vertices to Reach All Nodes

Medium Graphs Degree Counting Original on LeetCode

Reported atAirbnb

Minimum Number of Vertices to Reach All Nodes is a medium graphs problem solved with the degree counting pattern. The best approach, optimal (in-degree zero vertices), runs in O(n + E) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan all edges for every vertex) up.

Problem

You are given a directed acyclic graph with n vertices labelled 0 to n - 1 and a list edges, where edges[i] = [from, to] is a directed edge from from to to.

Find the smallest set of vertices from which every vertex in the graph can be reached by following edges. Such a set is guaranteed to be unique; return its vertices in any order.

Examples

Example 1

Input
n = 5, edges = [[0, 2], [2, 3], [1, 3], [3, 4]]
Output
[0, 1]
Why
No edge points into 0 or 1, so both must be chosen. From them, 2, 3 and 4 are all reachable.

Example 2

Input
n = 4, edges = [[1, 0], [2, 0], [3, 0]]
Output
[1, 2, 3]
Why
Vertex 0 has three incoming edges, but 1, 2 and 3 have none, and nothing else can reach them.

Example 3

Input
n = 6, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
Output
[0]
Why
A single chain: starting at its head reaches everything.

Constraints

  • 2 <= n <= 10^5
  • 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
  • edges[i] = [from, to] with 0 <= from, to < n, from != to
  • All edges are distinct and the graph has no directed cycle.
  • The answer is unique; it may be returned in any order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan all edges for every vertex)O(n · E)O(1)
Optimal (in-degree zero vertices)O(n + E)O(n)

1Brute force (scan all edges for every vertex)

TimeO(n · E)n vertices, each checked against all E edges.
SpaceO(1)Only the output list.

A vertex must be chosen exactly when nothing points to it. For each vertex, walk the entire edge list and check whether any edge ends there.

  1. For v = 0..n-1: look through every edge; if some edge has to == v, skip v.
  2. Otherwise add v to the answer.
class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> result = new ArrayList<>();
        for (int v = 0; v < n; v++) {
            boolean reached = false;
            for (List<Integer> e : edges) {
                if (e.get(1) == v) { reached = true; break; }
            }
            if (!reached) result.add(v);
        }
        return result;
    }
}

2Optimal (in-degree zero vertices)

TimeO(n + E)One pass over the edges, one pass over the vertices.
SpaceO(n)The boolean array.

Mark every vertex that is the target of some edge in one pass over the edges. The unmarked vertices have in-degree 0: each must be chosen, and together they reach every other vertex because walking backwards along incoming edges in a DAG always ends at one of them.

  1. Create a boolean array hasIncoming of size n.
  2. For every edge [from, to], set hasIncoming[to] = true.
  3. Return every v with hasIncoming[v] == false.
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> result = new ArrayList<>();
        for (int v = 0; v < n; v++) {
            if (!hasIncoming[v]) result.add(v);
        }
        return result;
    }
}

Edge cases to test

  • A vertex with no edges at all (it must be in the answer)
  • Many sources feeding one sink
  • A single chain (answer has exactly one vertex)
  • Several edges pointing into the same vertex

Hints

Hint 1

If no edge points into a vertex, which other start vertex could ever reach it?

Hint 2

Conversely, in a DAG every vertex with an incoming edge can be traced backwards to some vertex with no incoming edge.

Hint 3

So the answer is exactly the set of vertices with in-degree 0.

FAQ

What is the best time complexity for Minimum Number of Vertices to Reach All Nodes?

Optimal (in-degree zero vertices) runs in O(n + E) time and O(n) extra space. One pass over the edges, one pass over the vertices.

Which pattern does Minimum Number of Vertices to Reach All Nodes use?

It is a graphs problem that uses the degree counting pattern. Other problems with the same pattern: Find Center of Star Graph.

Is there a brute force solution for Minimum Number of Vertices to Reach All Nodes?

Yes. Brute force (scan all edges for every vertex) takes O(n · E) time and O(1) space. A vertex must be chosen exactly when nothing points to it.

Which edge cases should I test for Minimum Number of Vertices to Reach All Nodes?

A vertex with no edges at all (it must be in the answer); Many sources feeding one sink; A single chain (answer has exactly one vertex); Several edges pointing into the same vertex.