给你一个 有向无环图 , n
个节点编号为 0
到 n-1
,以及一个边数组 edges
,其中 edges[i] = [fromi, toi]
表示一条从点 fromi
到点 toi
的有向边。
找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。
你可以以任意顺序返回这些节点编号。
示例 1:
输入:n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
输出:[0,3]
解释:从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。
示例 2:
输入:n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
输出:[0,2,3]
解释:注意到节点 0,3 和 2 无法从其他节点到达,所以我们必须将它们包含在结果点集中,这些点都能到达节点 1 和 4 。
提示:
2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi < n
所有点对 (fromi, toi)
互不相同。
解题思路:
若一个图中的某一节点没有入度,则说明其它节点访问不到它,那么要遍历所有节点,他必须当第一个出发点,否则无法遍历它,而有入度的总会有节点能访问到,拿示例 1图来说:
图中打×的表示没有入度的节点,打√的则是有入度的节点
从节点0出发:0->1 0->2->5
从节点1出发:1
从节点2出发:2->5
从节点3出发:3->4->2->5
从节点4出发:4->3->5
从节点5出发:5
由分析可知:从所有有入度的节点(1,2,4,5)出发只会遍历1,2,4和5,因为入度不为零的点总可以由某个无入度的点到达,所以这些点不包括在最小的合法点集合当中。而从所有无入度节点(0,3)出发则能将节点全部遍历,因此我们只需要返回所有无入度的节点即可。
代码实现:
1.哈希表记录:
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
//哈希表记录所有有入度的点
Set<Integer> hs=new HashSet<>();
for(int x=0;x<edges.size();x++){
hs.add(edges.get(x).get(1));
}
List<Integer> l=new ArrayList<>();
//从零遍历,若该节点不在哈希表中说明,它为无入度节点,则存放到l中
for(int x=0;x<n;x++){
if(!hs.contains(x)){
l.add(x);
}
}
return l;
}
}
2.运用boolean数组记录:
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
//运用boolean类型数组存放,若有入度则为true
boolean []b=new boolean[n];
for(int x=0;x<edges.size();x++){
b[edges.get(x).get(1)]=true;
}
List<Integer> l=new ArrayList<>();
//false放进l中
for(int x=0;x<n;x++){
if(!b[x]) l.add(x);
}
return l;
}
}