Problem

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

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

Notice that you can return the vertices in any order.

Examples

Example 1:

1
2
3
4
5

Input:
n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output:
 [0,3]
Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].

Example 2:

1
2
3
4
5

Input:
n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output:
 [0,2,3]
Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.

Solution

Method 1 – In-degree Zero Nodes (1)

Intuition

The key idea is that in a directed acyclic graph, any node with in-degree zero cannot be reached from any other node. Thus, to reach all nodes, we must start from all nodes with in-degree zero.

Approach

  1. Initialize an array to track the in-degree of each node.
  2. For each edge, increment the in-degree of the destination node.
  3. Collect all nodes with in-degree zero; these are the required starting vertices.
  4. Return this set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> indeg(n);
        for (auto& e : edges) indeg[e[1]]++;
        vector<int> ans;
        for (int i = 0; i < n; ++i) if (indeg[i] == 0) ans.push_back(i);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func findSmallestSetOfVertices(n int, edges [][]int) []int {
    indeg := make([]int, n)
    for _, e := range edges {
        indeg[e[1]]++
    }
    ans := []int{}
    for i := 0; i < n; i++ {
        if indeg[i] == 0 {
            ans = append(ans, i)
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        int[] indeg = new int[n];
        for (List<Integer> e : edges) indeg[e.get(1)]++;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) ans.add(i);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun findSmallestSetOfVertices(n: Int, edges: List<List<Int>>): List<Int> {
        val indeg = IntArray(n)
        for (e in edges) indeg[e[1]]++
        val ans = mutableListOf<Int>()
        for (i in 0 until n) if (indeg[i] == 0) ans.add(i)
        return ans
    }
}
1
2
3
4
5
6

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: list[list[int]]) -> list[int]:
        indeg = [0] * n
        for u, v in edges:
            indeg[v] += 1
        return [i for i in range(n) if indeg[i] == 0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn find_smallest_set_of_vertices(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
        let n = n as usize;
        let mut indeg = vec![0; n];
        for e in edges.iter() {
            indeg[e[1] as usize] += 1;
        }
        let mut ans = vec![];
        for i in 0..n {
            if indeg[i] == 0 {
                ans.push(i as i32);
            }
        }
        ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    findSmallestSetOfVertices(n: number, edges: number[][]): number[] {
        const indeg = Array(n).fill(0);
        for (const [_, v] of edges) indeg[v]++;
        const ans: number[] = [];
        for (let i = 0; i < n; i++) if (indeg[i] === 0) ans.push(i);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the number of nodes and m is the number of edges; we process each edge and node once.
  • 🧺 Space complexity: O(n), for the in-degree array and answer list.