Pythonを使用してすべてのノードに到達するための頂点の最小数を見つけるプログラム

n個の頂点とノードに0からn-1までの番号が付けられた有向非巡回グラフがあるとします。グラフはエッジリストで表されます。ここで、edges [i] =（u、v）はノードuからノードv。グラフ内のすべてのノードに到達できる頂点の最小セットを見つける必要があります。 （頂点は任意の順序で返すことができます）。

したがって、入力が次のような場合

これらの2つの頂点は他のどの頂点からも到達できないため、出力は[0,2,3]になります。したがって、それらから開始すると、すべてをカバーできます。

これを解決するには、次の手順に従います-

• n：=エッジのサイズ

• all_nodes：=0からnまでの新しいセット

• v：=新しいセット

• エッジ内の各エッジ（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}