We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Vertices to Reach All Nodes

Number: 1661

Difficulty: Medium

Paid? No

Companies: Google, Adobe, Airbnb

Problem Description

Given a directed acyclic graph with n vertices labeled from 0 to n-1 and an array of directed edges, find the smallest set of vertices from which all nodes in the graph are reachable. It is guaranteed that a unique solution exists, and the vertices in the output can be in any order.

Key Insights

  • In a graph, if a node does not have any incoming edge, it cannot be reached from any other node.
  • Therefore, the minimal set of starting vertices must include all nodes with no incoming edges.
  • By iterating over all edges once, we can mark which vertices have incoming edges.
  • The final answer is simply the collection of vertices that were never targeted by any edge.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of vertices and m is the number of edges
Space Complexity: O(n) for tracking which vertices have incoming edges

Solution

The solution uses a simple array or list to track nodes that have incoming edges. The algorithm works as follows:

  1. Initialize an array of size n with all values set to false to indicate that initially no node is known to have an incoming edge.
  2. Iterate through each edge [u, v] and mark the target node v as having an incoming edge.
  3. After processing all edges, any node that is still marked false does not have any incoming edges and must be part of the minimal set.
  4. Return these nodes as the answer.

Data structures used: an array (or list) of booleans; algorithmic approach: single pass marking and collection.

Code Solutions

def findSmallestSetOfVertices(n, edges):
    # Create a list to track if a vertex has an incoming edge
    has_incoming = [False] * n

    # Mark each vertex that has an incoming edge by iterating over edges
    for edge in edges:
        from_node, to_node = edge  # edge represented as [from, to]
        has_incoming[to_node] = True

    # Collect vertices that do not have an incoming edge
    result = []
    for vertex in range(n):
        if not has_incoming[vertex]:
            result.append(vertex)
            
    return result

# Example usage:
# n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
# print(findSmallestSetOfVertices(n, edges))  # Expected output: [0, 3]
← Back to All Questions