#1557

Medium

auto_awesomeGraph-driven solution strategy

LeetCode Problem Workspace

Minimum Number of Vertices to Reach All Nodes

Identify the minimum set of vertices in a directed acyclic graph from which all nodes are reachable efficiently using graph analysis.

graph

Problem Statement

Given a directed acyclic graph with n nodes numbered from 0 to n-1, and a list of directed edges edges where each edge is represented as [from, to], determine the minimal set of vertices from which all nodes can be reached. Each edge describes a one-way connection, and the graph contains no cycles.

Return any order of vertices forming this minimal set. It is guaranteed that a unique solution exists, and your task is to identify the essential nodes whose inclusion ensures that every node is reachable starting from them.

Examples

Example 1

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

Output: [0,3]

It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].

Example 2

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

Output: [0,2,3]

Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.

Constraints

2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi < n
All pairs (fromi, toi) are distinct.

Solution Approach

Identify Source Nodes

Nodes with zero incoming edges are the only candidates that cannot be reached from any other node. Iterate through the edges to track in-degrees and collect all nodes with zero in-degree as initial sources.

Construct Minimum Vertex Set

After identifying source nodes, include each in the result set. Since every other node has at least one incoming edge, this ensures that all nodes can be reached directly or indirectly from the selected sources, forming the minimal vertex set.

Optimization and Complexity

By only scanning edges once to compute in-degrees and collecting zero in-degree nodes, the algorithm runs in O(n + m) time and O(n) space, avoiding unnecessary graph traversal and ensuring the solution scales to large DAGs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) where n is the number of nodes and m is the number of edges, as each edge is inspected once to compute in-degrees. Space complexity is O(n) to store in-degree counts and the result set of source vertices.

What Interviewers Usually Probe

Look for nodes with no incoming edges as a hint for mandatory inclusion.
Consider in-degree counting to avoid full traversal of the DAG.
Check that adding any other node does not reduce the minimal vertex set size.

Common Pitfalls or Variants

Common pitfalls

Assuming any node can be included without checking in-degree may lead to non-minimal sets.
Forgetting that DAG property guarantees a unique minimal solution, leading to unnecessary complexity.
Attempting full BFS/DFS from every node increases time and risks TLE for large graphs.

Follow-up variants

Find the minimum set of vertices to reach all nodes in a graph that may have cycles, requiring cycle detection.
Compute the minimal vertex set in a weighted DAG where edges have costs, prioritizing coverage by minimal total weight.
Determine the smallest vertex set for a dynamic DAG where edges are added incrementally and the set must be updated efficiently.

FAQ

How do I determine which nodes must be included to reach all nodes in a DAG?

Focus on nodes with zero incoming edges. These are the only nodes that cannot be reached from any other node and must be part of the minimal set.

Can the minimal set include nodes with incoming edges?

No, nodes with incoming edges are reachable from other nodes, so including them is unnecessary for the minimal set.

Does the order of nodes in the output matter?

No, the problem allows any order of vertices as long as the minimal set covers all nodes.

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

Using in-degree counting, you can achieve O(n + m) time complexity, scanning all nodes and edges only once.

Why is the solution guaranteed to be unique?

Because each node without incoming edges must be included and all others are reachable from them, forming a deterministic minimal set.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        cnt = Counter(t for _, t in edges)
        return [i for i in range(n) if cnt[i] == 0]

Continue Practicing

#1579 remove max number of edges to keep graph fully traversable #1584 min cost to connect all points #1591 strange printer ii