medium

Minimum Number of Vertices to Reach All Nodes

Find the smallest set of starting nodes that reaches everything by collecting exactly the nodes with no arrow pointing at them.

1. Define the problem

Minimum Number of Vertices to Reach All Nodes

You are given a directed graph with n nodes numbered 0 to n - 1 and a list of one-way edges, where [a, b] means you can travel from a to b. The graph has no cycles. Return the smallest set of starting nodes from which every node in the graph can be reached. You never have to explore anything. A node with no arrow pointing at it can only be reached by starting there, so it must be in the answer. Every other node already has something pointing at it, so it is covered. Collect the nodes with no incoming edges and you are done.

Constraints

  • 2 ≤ n ≤ 105
  • 1 ≤ edges.length ≤ min(105, n * (n - 1) / 2)
  • Each edge is a pair [from, to] with from not equal to to
  • All pairs are different and the graph has no cycles

Example

Inputn = 6, edges = [[0, 1], [0, 2], [2, 5], [3, 4], [4, 2]]
Output[0, 3]

Explanation Nodes 1, 2, 4 and 5 all have an arrow pointing at them, so something else can reach them. Nodes 0 and 3 have none, so they must both be starting points.

2. Know the words first

In plain terms

In-degree
How many arrows point at a node. A node with an in-degree of zero has no way in from anywhere else.
Reachable
A node you can arrive at by following arrows from some starting node.
Acyclic
Having no loops. Without loops, following arrows backwards from any node always ends at a node with no arrows in.
Minimal set
The smallest collection that still does the job. Here, dropping any node with in-degree zero would leave that node unreachable.
3. Visualize the solution

One cell per node, value = whether any arrow points at that node

One cell per node, value = whether any arrow points at that node
Statusinit

Six nodes, and no edges read yet, so nothing has an arrow pointing at it.

What happens in this step

n = 6
edges = [[0, 1], [0, 2], [2, 5], [3, 4], [4, 2]]
hasIncoming = no for every node

Every node starts as a candidate for the answer.
Step 1 of 6

Steps to visualize

  1. The row has one cell per node, labelled with the node number.
  2. The value is "no" while nothing points at that node and "yes" once something does.
  3. Read each edge and mark only its second node, because that is the end the arrow points at.
  4. The first node of an edge is ignored completely, which is why this runs in one quick pass.
  5. When all edges are read, every node still showing "no" belongs in the answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per node, value = whether any arrow points at that node
Statusinit

Six nodes, and no edges read yet, so nothing has an arrow pointing at it.

What happens in this step

n = 6
edges = [[0, 1], [0, 2], [2, 5], [3, 4], [4, 2]]
hasIncoming = no for every node

Every node starts as a candidate for the answer.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function findSmallestSetOfVertices(n, edges) {
  const hasIncoming = new Array(n).fill(false);

  for (const edge of edges) {
    hasIncoming[edge[1]] = true;
  }

  const result = [];

  for (let node = 0; node < n; node++) {
    if (!hasIncoming[node]) {
      result.push(node);
    }
  }

  return result;
}
Time
O(n + e), where e is the number of edges
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
n = 6, edges = [[0, 1], [0, 2], [2, 5], [3, 4], [4, 2]][0, 3]example from the docstring
n = 5, edges = [[0, 1], [2, 1], [3, 1], [1, 4], [2, 4]][0, 2, 3]several nodes pointing at the same target
n = 3, edges = [][0, 1, 2]no edges at all, so every node is its own starting point
n = 1, edges = [][0]the smallest graph there is
n = 3, edges = [[0, 1], [1, 2]][0]a chain where one start covers everything
n = 4, edges = [[0, 1], [2, 3]][0, 2]two separate pieces, each needing its own start

Keep reading