Minimum Number of Vertices to Reach All Nodes

Minimum Number of Vertices to Reach All Nodes - Problem

Graph Medium

Given a directed acyclic graph (DAG) with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from_i, to_i] represents a directed edge from node from_i to node to_i.

Find the smallest set of vertices from which all nodes in the graph are reachable. It is guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Input & Output

Example 1 — Basic DAG

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

› Output: [0,4]

💡 Note: From vertex 0, we can reach vertices 1, 2, and 3. From vertex 4, we can reach vertex 5. Vertices 0 and 4 have no incoming edges, so they must be in the minimum set.

Example 2 — Single Chain

$ Input: n = 3, edges = [[0,1],[1,2]]

› Output: [0]

💡 Note: This forms a chain 0→1→2. Starting from vertex 0, we can reach all vertices. Only vertex 0 has indegree 0.

Example 3 — No Edges

$ Input: n = 4, edges = []

› Output: [0,1,2,3]

💡 Note: With no edges, all vertices are isolated. Each vertex can only reach itself, so all vertices must be in the minimum set.

Constraints

2 ≤ n ≤ 10⁵
1 ≤ edges.length ≤ min(10⁵, n * (n - 1) / 2)
edges[i].length == 2
0 ≤ from_i, to_i < n
All pairs (from_i, to_i) are distinct.
The input represents a valid DAG.

Visualization

Tap to expand

Understanding the Visualization

Input DAG

Directed acyclic graph with n=6 vertices and edges

Analyze Indegrees

Count incoming edges for each vertex

Minimum Set

Vertices with indegree 0 form the answer

Key Takeaway

🎯 Key Insight: Vertices with no incoming edges cannot be reached from other vertices, so they must be included in the minimum set

Asked in

F Facebook 15 G Google 12 a Amazon 8

The key insight is that vertices with no incoming edges cannot be reached from any other vertex, so they must be in the minimum set. The optimal approach counts indegrees and returns all vertices with indegree 0. Time: O(n + m), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Indegree Analysis	O(n + m)	O(n)	Find vertices with no incoming edges - they must be in minimum set
Brute Force - Try All Combinations	O(2ⁿ × (n + m))	O(n + m)	Generate all possible subsets and find minimum that reaches all nodes

Indegree Analysis — Algorithm Steps

Count incoming edges for each vertex
Collect all vertices with indegree = 0
Return this set as the minimum vertices

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Indegrees

For each edge, increment indegree of destination vertex

Identify Zero Indegree

Find vertices with no incoming edges

Minimum Set

These vertices form the minimum set needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int n, int** edges, int edgesSize, int* returnSize) {
    // Count indegree for each vertex
    int* indegree = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < edgesSize; i++) {
        indegree[edges[i][1]]++;
    }
    
    // Vertices with indegree 0 must be in minimum set
    int* result = (int*)malloc(n * sizeof(int));
    *returnSize = 0;
    
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            result[(*returnSize)++] = i;
        }
    }
    
    free(indegree);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simplified input parsing for demonstration
    int edgesSize = 0;
    int** edges = NULL;
    
    // For a real implementation, parse the edges array from input
    int returnSize;
    int* result = solution(n, edges, edgesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through edges to count indegrees, then scan all vertices

✓ Linear Growth

Space Complexity

O(n)

Array to store indegree count for each vertex

⚡ Linearithmic Space

71.2K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Indegree Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler