Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで有向グラフを反転するプログラム

有向グラフがあるとすると、その逆を見つける必要があるため、エッジがuからvに移動すると、vからuに移動します。ここで入力は隣接リストになり、ノードがn個ある場合、ノードは（0、1、...、n-1）になります。

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

Pythonで有向グラフを反転するプログラム

その場合、出力は次のようになります

Pythonで有向グラフを反転するプログラム

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

  • ans：=n個の異なるリストのリスト。nは頂点の数です
  • 各インデックスi、およびグラフ内の隣接リストlについて、実行します
    • lのxごとに、
      • ans [x]
        • の最後にiを挿入します
  • 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, graph):
      ans = [[] for _ in graph]
      for i, l in enumerate(graph):
         for x in l:
            ans[x].append(i)
      return ans
ob = Solution()
graph = [[1,2],[4],[4],[1,2],[3]]
print(ob.solve(graph))

入力

[[1,2],[4],[4],[1,2],[3]]

出力

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

  1. 行列の転置を見つけるPythonプログラム

    この記事では、特定の問題ステートメントを解決するための解決策とアプローチについて学習します。 問題の説明 行列が与えられた場合、転置を同じ行列に格納して表示する必要があります。 行列の転置は、行を列に、列を行に変更することで得られます。つまり、A行列の転置はA[i][j]をA[j][i]に変更することで得られます。 以下に示す実装を見てみましょう- 例 N = 4 def transpose(A):    for i in range(N):       for j in range(i+1, N):     &nbs

  2. 配列の合計を見つけるPythonプログラム

    この記事では、特定の問題ステートメントを解決するための解決策とアプローチについて学習します。 問題の説明 入力として配列が与えられた場合、与えられた配列の合計を計算する必要があります。 ここでは、ブルートフォースアプローチに従うことができます。つまり、リストをトラバースし、各要素を空の合計変数に追加します。最後に、合計の値を表示します。 以下で説明するように、組み込みの合計関数を使用して別のアプローチを実行することもできます。 例 # main arr = [1,2,3,4,5] ans = sum(arr,n) print ('Sum of the array is '