可以到达所有点的最少点数目
难度:
标签:
题目描述
给你一个 有向无环图 ， 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^51 <= edges.length <= min(10^5, n * (n - 1) / 2)edges[i].length == 20 <= fromi, toi < n- 所有点对
(fromi, toi)互不相同。
代码结果
运行时间: 73 ms, 内存: 41.4 MB
/*
* 思路：
* 在有向无环图中，只有入度为0的点无法被其他点到达。我们需要找到这些点，并返回它们的集合。
* 因此，我们可以通过计算每个节点的入度，并将所有入度为0的节点加入结果集。
* 使用Java Stream API实现。
*/
import java.util.*;
import java.util.stream.*;
public class MinimumVerticesToReachAllNodesStream {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
// 记录每个节点的入度
int[] indegree = new int[n];
edges.forEach(edge -> indegree[edge.get(1)]++);
// 找到所有入度为0的节点
return IntStream.range(0, n)
.filter(i -> indegree[i] == 0)
.boxed()
.collect(Collectors.toList());
}
}
解释
方法:
该题目要求找到最少的点集，使得从这些点出发可以到达图中的所有节点。在有向无环图中，可以直接利用入度的概念来解决。入度为零的节点没有其他节点指向它，因此这些节点必须被包含在答案中，以确保从这些点出发可以访问到所有其他可达的节点。算法首先初始化一个记录每个节点入度的数组，然后遍历所有边，对每条边的终点节点的入度加一。最后，遍历入度数组，将入度为零的节点加入结果列表，这些就是所求的最小点集。
时间复杂度:
O(m + n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在此题目中，选择入度为零的节点作为起始点可以保证覆盖所有节点？
▷🦆
如果图中存在孤立节点（没有任何入边和出边的节点），该算法如何处理？
▷🦆
在算法实现中，是否考虑了图中可能存在的自环（即从一个节点指向其自身的边）对入度计算的影响？
▷🦆
在创建入度数组时，为什么可以直接使用n个元素初始化，而不需要考虑节点编号可能不连续的情况？
▷