使用Python查找到达所有节点所需的最小顶点数的程序

假设我们有一个有向无环图，其中有n个节点，节点从0到n-1编号，该图由边缘列表表示，其中edges[i] = (u,v)表示从节点u到节点v的有向边缘。我们必须找到最小的节点集，从该节点集中可达到图中的所有节点。（我们可以按任何顺序返回顶点）。

因此，如果输入如下所示：

那么输出将是[0,2,3]，因为这两个顶点无法从其他任何顶点到达，所以如果我们从它们开始，我们可以覆盖所有顶点。

为了解决此问题，我们将按照以下步骤进行操作:

• n: = edges的大小

• all_nodes：0到n的新集合

• v：一个新的集合

• 对于边缘中的每个（i，j），执行以下操作

  • 将j添加到v中
• ans：从all_nodes和v中删除所有公共边缘

• 返回答案

让我们看以下实现以更好地理解。

示例

def solve(edges):
  n = len(edges)
  all_nodes = set(range(n))
  v = set()
  for edge in edges:
     v.add(edge[1])
  ans = all_nodes - v
  return ans
edges = [(0,1),(2,1),(3,1),(1,4),(2,4)]
print(solve(edges))

输入

[(0,1),(2,1),(3,1),(1,4),(2,4)]

输出

{0,2,3}