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

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

✓ Brute Force - Try All Combinations

⏱️ Time: O(2ⁿ × (n + m)) Space: O(n + m)

Try every possible combination of vertices as starting points. For each combination, perform DFS/BFS to check if all nodes are reachable. Keep track of the smallest valid combination.

Indegree Analysis

⏱️ Time: O(n + m) Space: O(n)

The key insight is that any vertex with no incoming edges cannot be reached from any other vertex, so it must be included in the minimum set. Vertices with indegree 0 are exactly the minimum set needed.

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible subsets of vertices
For each subset, run DFS/BFS to check reachability
Return the smallest subset that reaches all nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all possible combinations of vertices

Test Reachability

For each subset, run DFS to check if all nodes reachable

Find Minimum

Return smallest subset that reaches all nodes

Code -

solution.c — C

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

#define MAX_N 1000
#define MAX_EDGES 10000

int graphAdj[MAX_N][MAX_N];
int graphSize[MAX_N];
int visited[MAX_N];
int visitedCount;
int totalN;

void dfs(int node) {
    if (visited[node]) return;
    visited[node] = 1;
    visitedCount++;
    for (int i = 0; i < graphSize[node]; i++) {
        dfs(graphAdj[node][i]);
    }
}

int canReachAll(int* startNodes, int startCount) {
    memset(visited, 0, sizeof(int) * totalN);
    visitedCount = 0;
    for (int i = 0; i < startCount; i++) {
        dfs(startNodes[i]);
    }
    return visitedCount == totalN;
}

int current[MAX_N];
int resultBuf[MAX_N];
int resultLen;
int found;

void generateCombinations(int start, int k, int currentSize) {
    if (found) return;
    if (k == 0) {
        if (canReachAll(current, currentSize)) {
            found = 1;
            resultLen = currentSize;
            memcpy(resultBuf, current, sizeof(int) * currentSize);
        }
        return;
    }
    for (int i = start; i <= totalN - k; i++) {
        current[currentSize] = i;
        generateCombinations(i + 1, k - 1, currentSize + 1);
        if (found) return;
    }
}

void solution(int n, int edges[][2], int edgeCount) {
    totalN = n;
    memset(graphSize, 0, sizeof(int) * n);

    for (int i = 0; i < edgeCount; i++) {
        int from = edges[i][0];
        int to = edges[i][1];
        graphAdj[from][graphSize[from]++] = to;
    }

    found = 0;
    for (int size = 1; size <= n; size++) {
        generateCombinations(0, size, 0);
        if (found) return;
    }

    /* Fallback: all nodes */
    resultLen = n;
    for (int i = 0; i < n; i++) {
        resultBuf[i] = i;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    /* consume rest of line after n */
    {
        int c;
        while ((c = getchar()) != '\n' && c != EOF);
    }

    char line[100000];
    fgets(line, sizeof(line), stdin);

    int edges[MAX_EDGES][2];
    int edgeCount = 0;

    /* Parse exactly like C++: find inner [...] pairs */
    if (strcmp(line, "[]\n") != 0 && strcmp(line, "[]") != 0) {
        /* Remove outer brackets: skip first '[' */
        char* p = strchr(line, '[');
        if (p) p++; /* skip outer '[' */

        while (p && *p) {
            /* Find inner '[' */
            char* innerStart = strchr(p, '[');
            if (!innerStart) break;
            innerStart++; /* skip '[' */

            /* Find matching ']' */
            char* innerEnd = strchr(innerStart, ']');
            if (!innerEnd) break;

            /* Extract content between [ and ] */
            char buf[64];
            int len = (int)(innerEnd - innerStart);
            strncpy(buf, innerStart, len);
            buf[len] = '\0';

            /* Parse "from,to" */
            int from = -1, to = -1;
            char* comma = strchr(buf, ',');
            if (comma) {
                *comma = '\0';
                from = atoi(buf);
                to = atoi(comma + 1);
            }

            if (from >= 0 && to >= 0) {
                edges[edgeCount][0] = from;
                edges[edgeCount][1] = to;
                edgeCount++;
            }

            p = innerEnd + 1;
        }
    }

    solution(n, edges, edgeCount);

    /* Output exactly like C++: [0,1,2] */
    printf("[");
    for (int i = 0; i < resultLen; i++) {
        printf("%d", resultBuf[i]);
        if (i < resultLen - 1) printf(",");
    }
    printf("]\n");

    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × (n + m))

2^n subsets to try, each requires O(n+m) DFS traversal

✓ Linear Growth

Space Complexity

O(n + m)

Graph representation and DFS recursion stack

⚡ 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

Minimum Number of Vertices to Reach All Nodes - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler