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.

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:

Input:

  • Number of Nodes (n): 6
  • Edges: [[0,1], [0,2], [2,5], [3,4], [4,2]]

Execution Steps:

  1. Initialization:

    • Create hasIncomingEdge array of size 6: hasIncomingEdge = [false, false, false, false, false, false]

  2. Mark Nodes with Incoming Edges:

Process each edge and mark the destination node:

  • Edge [0,1]: hasIncomingEdge[1] = true
    • hasIncomingEdge = [false, true, false, false, false, false]
  • Edge [0,2]: hasIncomingEdge[2] = true
    • hasIncomingEdge = [false, true, true, false, false, false]
  • Edge [2,5]: hasIncomingEdge[5] = true
    • hasIncomingEdge = [false, true, true, false, false, true]
  • Edge [3,4]: hasIncomingEdge[4] = true
    • hasIncomingEdge = [false, true, true, false, true, true]
  • Edge [4,2]: hasIncomingEdge[2] = true (already true)
    • hasIncomingEdge = [false, true, true, false, true, true]

  1. Identify Nodes without Incoming Edges:

    • Iterate over all nodes (0 to 5) and check for hasIncomingEdge[i] == false:

      • Node 0: hasIncomingEdge[0] == false, so add 0 to result.
      • Node 1: hasIncomingEdge[1] == true, skip.
      • Node 2: hasIncomingEdge[2] == true, skip.
      • Node 3: hasIncomingEdge[3] == false, so add 3 to result.
      • Node 4: hasIncomingEdge[4] == true, skip.
      • Node 5: hasIncomingEdge[5] == true, skip.

    • Result list after iteration:

      result = [0, 3]

  2. Return the Result:

    • The final result is [0, 3].

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