1557. Minimum Number of Vertices to Reach All Nodes¶
题目信息¶
- 题号:
1557
- 难度:
Medium
- 主题:
有向无环图、入度、可达性
- 原题:
- 重点:
在有向无环图中,所有入度为零的节点必须作为起点,且这些节点足以到达全部节点
题目重述¶
给定包含 n 个节点的有向无环图,节点编号为 0 到 n-1,edges[i] = [from_i,to_i] 表示一条有向边。
请选择最少数量的起始节点,使从这些节点出发沿有向边能够访问图中全部节点。返回任意顺序的最小起点集合。
2 <= n <= 10^5,边数不超过 min(10^5,n(n-1)/2)。
自建示例¶
每个入度为零的连通来源都必须保留:
输入:n = 5, edges = [[0,1],[2,1],[3,4]]
输出:[0,2,3]
解释:节点 0、2、3 都没有入边,无法从其他节点到达。
没有边时每个节点都必须作为起点:
输入:n = 3, edges = []
输出:[0,1,2]
解释:任意节点都不能从另一个节点到达。