Minimum Number of Vertices to Reach All Nodes
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^51 <= edges.length <= min(10^5, n * (n - 1) / 2)edges[i] = [from, to]with0 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n · E)n vertices, each checked against all E edges.O(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.
- For v = 0..n-1: look through every edge; if some edge has
to == v, skip v. - 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;
}
}class Solution:
def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
result = []
for v in range(n):
reached = False
for e in edges:
if e[1] == v:
reached = True
break
if not reached:
result.append(v)
return resultclass Solution {
public:
vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
vector<int> result;
for (int v = 0; v < n; v++) {
bool reached = false;
for (auto& e : edges) {
if (e[1] == v) { reached = true; break; }
}
if (!reached) result.push_back(v);
}
return result;
}
};function findSmallestSetOfVertices(n, edges) {
const result = [];
for (let v = 0; v < n; v++) {
let reached = false;
for (const e of edges) {
if (e[1] === v) { reached = true; break; }
}
if (!reached) result.push(v);
}
return result;
}2Optimal (in-degree zero vertices)
O(n + E)One pass over the edges, one pass over the vertices.O(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.
- Create a boolean array
hasIncomingof size n. - For every edge
[from, to], sethasIncoming[to] = true. - 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;
}
}class Solution:
def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
has_incoming = [False] * n
for e in edges:
has_incoming[e[1]] = True
return [v for v in range(n) if not has_incoming[v]]class Solution {
public:
vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
vector<bool> hasIncoming(n, false);
for (auto& e : edges) hasIncoming[e[1]] = true;
vector<int> result;
for (int v = 0; v < n; v++) {
if (!hasIncoming[v]) result.push_back(v);
}
return result;
}
};function findSmallestSetOfVertices(n, edges) {
const hasIncoming = new Array(n).fill(false);
for (const e of edges) hasIncoming[e[1]] = true;
const result = [];
for (let v = 0; v < n; v++) {
if (!hasIncoming[v]) result.push(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.