使用 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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告