Design Gurus Logo
Solution: Minimum Number of Vertices to Reach All Nodes (medium)

Problem Statement

Given a directed acyclic graph with n nodes labeled from 0 to n-1, determine the smallest number of initial nodes such that you can access all the nodes by traversing edges. Return these nodes.

Examples

  1. Example 1:

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

  • Expected Output: [0,3]

Image
  • Justification: Starting from nodes 0 and 3, you can reach all other nodes in the graph. Starting from node 0, you can reach nodes 1, 2, and 5. Starting from node 3, you can reach nodes 4 and 2 (and by extension 5).
  1. Example 2:
  • Input:
    • n = 3
    • edges = [[0,1],[2,1]]
  • Expected Output: [0,2]
Image
  • Justification: Nodes 0 and 2 are the only nodes that don't have incoming edges. Hence, you need to start from these nodes to reach node 1.
  1. Example 3:
  • Input:
    • n = 5
    • edges = [[0,1],[2,1],[3,4]]
  • Expected Output: [0,2,3]
Image
  • Justification: Node 1 can be reached from both nodes 0 and 2, but to cover all nodes, you also need to start from node 3.

Constraints:

  • 2 <= n <= 10^5
  • 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= from<sub>i</sub>, to<sub>i</sub> < n
  • All pairs (from<sub>i</sub>, to<sub>i</sub>) are distinct.

Why this is a Graph problem

What the question saysThe signal it matches
"a directed acyclic graph with n nodes"the input describes connections with direction and no cycles
"the smallest number of initial nodes"any node with no incoming edge must be a starting point

This is the find the roots of a directed graph variant, and its second example states the answer directly: "the only nodes that don't have incoming edges".

The closest alternative. No traversal at all, and noticing that is the whole problem. The phrase "a directed acyclic graph with n nodes" removes the search. No cycles means no route returns to where it began. So a node with no incoming edge can never be reached from anywhere else, and it must be a start. Every other node needs no start of its own, because walking its incoming edges backwards must end at some root.

One pass over the edge list marks every node that appears as a destination. The unmarked nodes are the answer. With 100,000 edges that is one linear scan, where testing candidate starting sets would run a full traversal per candidate.

Solution

To solve the problem of determining the minimum number of vertices needed to reach all nodes in a directed graph, we focus on the concept of "in-degree" which represents the number of incoming edges to a node. In a directed graph, if a node doesn't have any incoming edges (in-degree of 0), then it means that the node cannot be reached from any other node. Hence, such nodes are mandatory starting points to ensure that every node in the graph can be reached. Our algorithm thus identifies all nodes with an in-degree of 0 as they are potential starting points to traverse the entire graph.

Step-by-Step Algorithm

  1. Initialization:

    • Create a boolean array hasIncomingEdge of size n initialized to false. This array tracks whether a node has any incoming edges.

  2. Mark Nodes with Incoming Edges:

    • For each edge in the edges list, set hasIncomingEdge[edge[1]] = true to indicate that the destination node of the edge has an incoming edge.

  3. Identify Nodes without Incoming Edges:

    • Initialize an empty list result to store nodes without incoming edges.
    • Iterate through all nodes from 0 to n-1:
      • If hasIncomingEdge[i] == false, add node i to the result list.

  4. Return the Result:

    • Return the result list as the smallest set of vertices from which all other nodes are reachable.

Algorithm Walkthrough

mediaLink

A node with an arrow pointing at it can be reached from somewhere else, so it never needs to be a starting point. A node with NO arrow pointing at it cannot be reached at all, so it must be one. That is the whole problem, and it needs no traversal to answer.

1 of 7

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

1. Mark Nodes with Incoming Edges

  • The first for loop iterates over all edges in the graph:
    • Each edge updates the hasIncomingEdge array in constant time O(1).
  • If the number of edges is denoted by E, this operation takes O(E) time.

2. Identify Nodes Without Incoming Edges

  • The second for loop iterates over all vertices in the graph:
    • Checking the hasIncomingEdge array for each node takes constant time O(1).
  • If the number of vertices is denoted by V, this operation takes O(V) time.

3. Overall Time Complexity

\text{Total Time Complexity} = O(E) + O(V)

Space Complexity

1. Boolean Array (hasIncomingEdge)

  • The hasIncomingEdge array has a size equal to the number of vertices, n.
  • Space Requirement: O(V).

2. Result List

  • The result list stores nodes without incoming edges.
  • In the worst case (e.g., a graph with no incoming edges), all vertices will be added to the list.
  • Space Requirement: O(V).

4. Overall Space Complexity

  • The total space required is: O(V)

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory