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

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

所以，如果输入类似于

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

为了解决这个问题，我们将遵循以下步骤 -

  • n := edges 的大小

  • all_nodes := 从 0 到 n 的范围创建一个新的集合

  • v := 一个新的集合

  • 对于 edges 中的每个边 (i, j)，执行以下操作

    • 将 j 添加到 v 中

  • ans := 从 all_nodes 中移除 all_nodes 和 v 的所有公共边

  • 返回 ans

让我们看看下面的实现来更好地理解 -

示例

 现场演示

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}

更新于: 2021年5月29日

401 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告