Domain 2MediumMEDIUM

Minimum Number of Vertices to Reach All Nodes

Identify all nodes with zero in-degree by marking destinations, as these are the only necessary starting points to reach every node.

Domain: medium•Updated: 2026-09-18
#indegree check#boolean array#$O(N+E)$ time complexity#$O(N)$ space complexity

Problem Breakdown

We need to find a subset of vertices such that traversing edges from this set allows us to visit all other nodes in the graph. The problem guarantees the graph is a Directed Acyclic Graph (DAG) and asks for the smallest such set.

  • Inputs:
    • n: Integer representing the number of vertices (00 to n−1n-1).
    • edges: List of directed edges [from, to].
  • Outputs: A list of integers representing indices of starting nodes (order does not matter).
  • Constraints & Guarantees:
    • Graph is a DAG.
    • 2≤n≤1052 \le n \le 10^5.
    • Unique solution exists.

Intuition

The core question is: “Which vertices do we absolutely need to start from?”

Consider any node v in the graph that has at least one incoming edge (in-degree ≥1\ge 1). This means there exists some path leading into v. If all nodes with an in-degree of 00 are included as starting points, then every other node is reachable because:

  1. Any node with an in-degree > 0 can be reached from its immediate predecessor.
  2. Following predecessors backwards eventually leads to a chain that must terminate at a node with no incoming edges (a source), due to the graph being finite and acyclic.

Therefore, nodes with in-degree = 0 are unreachable by any other vertex in the graph. They must be included in our starting set. Conversely, including all such sources is sufficient because every connected component of a DAG has at least one source node. Thus, finding vertices that never appear as to (destination) in any edge list solves the problem efficiently.

Approach

  1. Initialize Tracking Structure: Create a boolean array or hash set to track which nodes have incoming edges (has_incoming). Initialize all entries to False.
  2. Mark Destinations: Iterate through every [from, to] in the edges list. For each edge, mark node to as having an incoming edge (set its tracking value to True). We do not need to track from because we are looking for nodes that cannot be reached from others.
  3. Identify Sources: Iterate through all vertex indices 00 to n−1n-1. If a node’s entry in the tracking structure is still False, it means its in-degree is zero. Add this index to our result list.
  4. Return Result: Return the collected list of source nodes.

Complexity Analysis

  • Time Complexity: O(N+E)O(N + E), where NN is the number of vertices and EE is the length of edges.
    • We iterate through all edges once to mark destinations: O(E)O(E).
    • We iterate through all vertex indices (0…n−10 \dots n-1) exactly once to find those with zero in-degree: O(N)O(N).
  • Space Complexity: O(N)O(N) for the boolean array used to track incoming edge status. This is optimal as we need at least this much space to store reachability information without building an adjacency list (which would also take O(E)O(E)).

Solution

from typing import List

def min_set_of_vertices(n: int, edges: List[List[int]]) -> List[int]:
    # Use a boolean array to mark vertices that are destinations of at least one edge.
    # If a vertex is never marked here, it has an in-degree of 0 and must be included.
    has_incoming = [False] * n
    
    for _, target in edges:
        has_incoming[target] = True
        
    result = []
    
    # Collect all vertices that were not destinations (in-degree == 0)
    for i in range(n):
        if not has_incoming[i]:
            result.append(i)
            
    return result

# Example usage:
# print(min_set_of_vertices(6, [[0,1],[0,2],[2,5],[3,4],[4,2]])) # Output: [0, 3] (order may vary)

Edge Cases Handled

  • Disconnected Graphs: If the graph consists of multiple disconnected components, nodes in isolated subgraphs will naturally have an in-degree of zero and be correctly included.
  • Isolated Nodes: A node with no incoming or outgoing edges is treated as having 0 in-degree (never marked), so it is added to the result set, which is correct since we must start there to reach itself.
  • Large N (10510^5): The solution uses a linear pass over vertices and edges without recursion depth issues or excessive memory overhead, fitting within standard time limits for Python on FAANG platforms.