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 ( to ).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.
- .
- 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 ). This means there exists some path leading into v. If all nodes with an in-degree of are included as starting points, then every other node is reachable because:
- Any node with an in-degree > 0 can be reached from its immediate predecessor.
- 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
- Initialize Tracking Structure: Create a boolean array or hash set to track which nodes have incoming edges (
has_incoming). Initialize all entries toFalse. - Mark Destinations: Iterate through every
[from, to]in theedgeslist. For each edge, mark nodetoas having an incoming edge (set its tracking value toTrue). We do not need to trackfrombecause we are looking for nodes that cannot be reached from others. - Identify Sources: Iterate through all vertex indices to . 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. - Return Result: Return the collected list of source nodes.
Complexity Analysis
- Time Complexity: , where is the number of vertices and is the length of
edges.- We iterate through all edges once to mark destinations: .
- We iterate through all vertex indices () exactly once to find those with zero in-degree: .
- Space Complexity: 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 ).
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-degreeof 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 (): 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.