MediumGraph

Minimum Number of Vertices to Reach All Nodes

1 approach, code in every language

You are given a directed acyclic graph with n nodes labeled from 0 to n - 1, described by a list of directed edges where each edge [a, b] points from node a to node b. Starting from a chosen set of nodes and only walking along the direction of the edges, you want to be able to reach every node in the graph.

Return the smallest possible set of nodes from which all nodes are reachable. It is guaranteed that a unique solution exists.

You may return the nodes of the answer in any order.

Example 1

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

Output: [0,3]

From 0 you reach 1, 2, and 5; from 3 you reach 4 and then 2 and 5. Nodes 0 and 3 have no incoming edges, so they cannot be reached from anywhere else and must be included.

Example 2

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

Output: [0,2,3]

Nodes 0, 2, and 3 have indegree zero, so they must be starting points. From them nodes 1 and 4 are reachable, covering the entire graph.

Constraints

2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= a, b < n
a != b, and all edge pairs are unique
The graph is a directed acyclic graph (DAG)

Collect Zero-Indegree Nodes

A node can be reached from elsewhere only if it has an incoming edge, so the answer is exactly the set of nodes with indegree zero.

Loading animation…

Intuition

Think about which nodes we are forced to include. If a node has at least one incoming edge, then some other node points to it, so it is reachable without ever selecting it directly. That means we never need to include any node with a positive indegree. On the other hand, a node with indegree zero has no incoming edge at all, so nothing can reach it and it must be a starting point. Because the graph is acyclic, choosing all zero-indegree nodes is both necessary and sufficient to cover every node. So the whole problem reduces to counting incoming edges and returning the nodes that received none.

Algorithm walkthrough

1Create an indegree array of size n, all zeros.
2For every edge [a, b], increment indegree[b], since b has one more incoming edge.
3Scan every node from 0 to n - 1.
4Whenever a node's indegree is zero, add it to the answer because it cannot be reached from any other node.
5Return the collected list of zero-indegree nodes.

Implementation

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        indegree = [0] * n
        for _, v in edges:
            indegree[v] += 1
        return [i for i in range(n) if indegree[i] == 0]

Time

O(n + e)

Space

O(n)

e is the number of edges. One pass over the edges builds the indegree array and one pass over the nodes collects the answer. The indegree array uses O(n) space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free