介绍：

欢迎来到 LeetCode 问题世界的另一场激动人心的旅程！在本文中，我们将探讨第 1557 题：到达所有节点的最小顶点数。我们将仔细研究问题陈述，讨论解决它的策略方法，并提供解决方案的逐步分解。最后，你将清楚地了解如何找到可以到达有向无环图中所有节点的最小顶点集。让我们开始吧！

问题陈述：

给定一个有向无环图（DAG）和一个有向边数组，我们的任务是找到最小的顶点集，从该集合中所有节点都可达。每个有向边由一个数组 [from_i, to_i] 表示，表示从节点 from_i 到节点 to_i 的有向边。保证存在唯一的解，并且我们可以按任意顺序返回顶点。

方法：

为了高效地解决这个问题，我们可以遵循一个策略性的方法。我们将遍历有向边，并将目标节点标记为可达。最后，我们将返回未标记为可达的顶点集。让我们深入到伪代码和详细的解释中。

伪代码：

让我们看一下我们的方法的伪代码：

class Solution: def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]: # Initialize a set of reachable vertices reachable = set()

    # Iterate through the edges
    for edge in edges:
        # Mark the destination node as reachable
        reachable.add(edge[1])
    
    # Find the set of vertices that are not marked as reachable
    result = []
    for vertex in range(n):
        if vertex not in reachable:
            result.append(vertex)
    
    return result

详细解释：

• 我们定义了一个 findSmallestSetOfVertices 函数，该函数以顶点数 n 和边数组作为参数。它返回最小的顶点集，从该集合中所有节点都可达。
• 我们初始化一个名为 reachable 的集合，以跟踪可达顶点。
• 我们使用循环遍历 edges 数组。对于每个有向边，我们将目标节点（edge [1]）添加到 reachable 集合中。
• 在标记可达顶点之后，我们创建一个名为 result 的空列表，用于存储未标记为可达的顶点。
• 我们使用循环遍历从 0 到 n-1 的所有顶点。如果一个顶点不在 reachable 集合中，则将其附加到 result 列表中。
• 最后，我们返回包含未标记为可达的顶点的 result 列表。

复杂度分析：

• 时间复杂度：该算法遍历边和顶点，导致时间复杂度为 O(E+V)，其中 E 是边数，V 是顶点数。
• 空间复杂度：空间复杂度为 O(V)，其中 V 是顶点数，因为我们将可达顶点存储在一个集合中。

解决方案

Python

class Solution:
    def findSmallestSetOfVertices(self, n: int, neighbors: List[List[int]]) -> List[int]:
        unreachables = set([i for i in range(n)])
        zero_indegree_nodes = set([i for i in range(n)])
        edges = {}
        for entry in neighbors:
            if entry[0] not in edges:
                edges[entry[0]] = []
            edges[entry[0]].append(entry[1])
            zero_indegree_nodes.discard(entry[1])
        # step 1: find all vertices with indegree = 0, traverse them and mark up reachable nodes
        result = list(zero_indegree_nodes)
        for node in zero_indegree_nodes:
            self._explore(node, unreachables, edges)
        # step 2: the rests are loops that are not connected -- also traverse and mark up
        while unreachables:
            result.append(min(unreachables))
            self._explore(min(unreachables), unreachables, edges)
        
        return sorted(result)
    
    def _explore(self, node, not_seen, edges):
        if node not in not_seen:
            return
        not_seen.remove(node)
        if node in edges:
            for neighbor in edges[node]:
                self._explore(neighbor, not_seen, edges)

findSmallestSetOfVertices 函数接受两个参数：n，图中顶点的数量，以及 neighbors，表示图的邻接列表的有向边列表。

初始化：

• unreachables：一个集合，最初包含从 0 到 n-1 的所有顶点，表示尚未到达的顶点。
• zero_indegree_nodes：一个集合，最初包含从 0 到 n-1 的所有顶点，表示入度为 0 的顶点。
• edges：一个字典，将每个顶点映射到其出边的列表。它是从 neighbors 列表构建的。

找到入度为 0 的顶点：

• 对于 neighbors 列表中的每个条目，代码检查源顶点（entry [0]）是否存在于 edges 字典中。如果不存在，则为该顶点添加一个空列表。
• 它将目标顶点（entry [1]）附加到源顶点的出边列表中。
• 它还从 zero_indegree_nodes 集合中删除目标顶点，因为它具有入边。

步骤 1：从入度为 0 的顶点中找到可达节点：

• 代码使用 zero_indegree_nodes 中的每个顶点 node，调用 _explore 函数递归地标记从 node 可达的节点。它将 unreachables 集合和 edges 字典作为参数传递。
• _explore 函数从 not_seen 集合中删除当前 node，并递归地探索其邻居，同时将其标记为已见过。

步骤 2：找到不连通的循环：

• 代码进入一个 while 循环，直到 unreachables 集合为空为止。
• 在每次迭代中，它将 unreachables 中的最小值附加到 result 列表中。这确保顶点按升序添加。
• 它为最小顶点调用 _explore 函数，以标记从该顶点可达的所有节点。

返回结果：

• 代码以升序排序的方式返回 result 列表。

_explore 函数是一个帮助函数，用于递归地标记从给定顶点可达的节点。它以 node 作为参数，并通过删除已探索的顶点来修改 not_seen 集合。它还递归调用当前 node 的邻居。

总的来说，该代码有效地找到了最小的顶点集，从该集合中所有节点都可达。它使用了找到入度为 0 的顶点和递归地探索图的组合。

Java

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> ans = new ArrayList<Integer>();
        Set<Integer> endset = new HashSet<Integer>();

        for (List<Integer> edge: edges) {
            endset.add(edge.get(1));
        }

        for (int i = 0; i < n; ++i) {
            if (!endset.contains(i)) {
                ans.add(i);
            }
        }
        return ans;
    }
}
// 

C++

class Solution {
public:
     vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> res, seen(n);
        for (auto& e: edges)
            seen[e[1]] = 1;
        for (int i = 0; i < n; ++i)
            if (seen[i] == 0)
                res.push_back(i);
        return res;
    }
};

findSmallestSetOfVertices 函数接受两个参数：n，图中顶点的数量，以及 edges，表示图中有向边的向量的向量。- 初始化：

• res：一个空的向量，用于存储结果，即最小的顶点集合。
• seen：一个大小为 n 的向量，表示每个顶点是否被访问过。最初，所有元素都被设置为 0。

2. 标记具有入边的顶点：

• 代码迭代遍历 edges 向量中的每个向量 e。
• 它将目标顶点（e[1]）的 seen 值设置为 1，表示它具有入边。

3. 查找没有入边的顶点：

• 代码从 0 到 n-1 迭代并检查当前顶点（i）的 seen 值是否为 0，表示它没有入边。
• 如果 seen 值为 0，则将当前顶点 i 推入 res 向量中。

4. 返回结果：

• 代码返回 res 向量，其中包含没有入边的最小顶点集合。

这段代码利用了一个事实：如果一个顶点有入边，则它不能是能到达所有节点的最小顶点集合的一部分。因此，它只标记具有入边的顶点，然后返回未标记的顶点（即 seen 值为 0 的顶点）。

总的来说，这段代码通过直接识别没有入边的顶点，而不需要递归探索或额外的数据结构，提供了一个简洁而高效的解决方案来解决这个问题。

结论：

在本文中，我们探讨了在有向无环图（DAG）中找到从所有节点可达的最小顶点集合的问题。通过标记有向边的目标节点并返回未标记的顶点，我们有效地解决了这个问题。我们详细解释了伪代码的每个部分，提供了详细的解决方案分解。

理解有向无环图和掌握问题解决技巧是任何程序员的宝贵技能。通过持续练习和探索 LeetCode 问题，你将锻炼你的问题解决能力，并变得熟练于解决复杂的编码挑战。

不断挑战自己的极限，拥抱挑战！