1557. Minimum Number of Vertices to Reach All Nodes

1557. Minimum Number of Vertices to Reach All Nodes

Question

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from i, to] 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’s guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Answer

由于是有向无环图(Directed acyclic graph),因此直接计算图内的入度为0的节点即可。
每条路径都需要从入度为0的点开始。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
List<Integer> ret = new ArrayList<>();
int[] inDegrees = new int[n];
for(List<Integer> edge : edges){
inDegrees[edge.get(1)]++;
}
for(int i = 0; i < n; i++){
if(inDegrees[i] == 0) ret.add(i);
}
return ret;
}
}
Author

Xander

Posted on

2022-05-04

Updated on

2022-05-04

Licensed under

Comments