Medium

题目描述

给你一个有向无环图，有 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的节点：没有任何边指向它们的节点只能由自己到达
  2. 入度非0的节点：至少有一条边指向它们，说明可以从其他节点到达
  3. 最优策略：我们只需要选择所有入度为0的节点作为起始点

算法思路

由于题目要求找到能到达所有节点的最小顶点集，我们需要分析哪些节点是"必须"的起始点：

  • 如果一个节点有入度（即有其他节点指向它），那么它可以从其他节点到达，不需要作为起始点
  • 如果一个节点入度为0，那么只能从它自己开始才能访问到它

因此，答案就是所有入度为0的节点。这个贪心策略是最优的，因为：

  1. 入度为0的节点必须包含在答案中（没有其他方式到达它们）
  2. 入度非0的节点都可以从某个入度为0的节点通过路径到达

算法步骤：

  1. 统计每个节点的入度
  2. 收集所有入度为0的节点
  3. 返回结果

代码实现

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> inDegree(n, 0);
        
        // 统计每个节点的入度
        for (auto& edge : edges) {
            inDegree[edge[1]]++;
        }
        
        vector<int> result;
        // 找到所有入度为0的节点
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        in_degree = [0] * n
        
        # 统计每个节点的入度
        for edge in edges:
            in_degree[edge[1]] += 1
        
        # 找到所有入度为0的节点
        result = []
        for i in range(n):
            if in_degree[i] == 0:
                result.append(i)
        
        return result

public class Solution {
    public IList<int> FindSmallestSetOfVertices(int n, IList<IList<int>> edges) {
        int[] inDegree = new int[n];
        
        // 统计每个节点的入度
        foreach (var edge in edges) {
            inDegree[edge[1]]++;
        }
        
        List<int> result = new List<int>();
        // 找到所有入度为0的节点
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

var findSmallestSetOfVertices = function(n, edges) {
    const inDegree = new Array(n).fill(0);
    
    // 统计每个节点的入度
    for (const edge of edges) {
        inDegree[edge[1]]++;
    }
    
    const result = [];
    // 找到所有入度为0的节点
    for (let i = 0; i < n; i++) {
        if (inDegree[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(V + E)
空间复杂度O(V)

其中 V 是顶点数量（n），E 是边的数量（edges.length）。时间复杂度中，我们需要遍历所有边来计算入度，然后遍历所有顶点来找入度为0的节点。空间复杂度主要用于存储入度数组。