Pythonでグラフを切断するエッジを見つけるためのプログラム

隣接リストとして表された無向グラフが提供されたとします。ここで、graph[i]はノードiの隣接ノードを表します。次の条件を満たすエッジの数を見つける必要があります。

エッジを削除すると、グラフが切断されます。

So, if the input is like graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
],

その場合、出力は1になります。

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

• 関数dfs（）を定義します。これにはcurr、pre、dが必要です

  • ans：=無限大

  • dep [curr]：=d

  • グラフ[curr]の各調整について、実行

    • preがadjと同じ場合、

      • 他の手順を実行せずに次の反復を続行します

    • dep [adj]が-1と同じでない場合、

      • ans：=最小のans、dep [adj]

    • それ以外の場合

      • ans：=最小のans、dfs（adj、curr、d + 1）

  • d>0かつd<=ansの場合、

    • re：=re + 1

  • ansを返す

• ここで、メイン関数から関数dfs（）を呼び出します。

• dep：=-1で初期化されたグラフのサイズのリスト。

• re：=0

• dfs（0、-1、0）

• 戻る

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

例

class Solution:
   def solve(self, graph):
      dep = [−1] * len(graph)
      INF = int(1e9)
      self.re = 0
      def dfs(curr, pre, d):
         ans = INF
         dep[curr] = d
         for adj in graph[curr]:
            if pre == adj:
               continue
            if dep[adj] != −1:
               ans = min(ans, dep[adj])
            else:
               ans = min(ans, dfs(adj, curr, d + 1))
         if d > 0 and d <= ans:
            self.re += 1
         return ans
      dfs(0, −1, 0)
      return self.re
ob = Solution()
print(ob.solve(graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
]))

入力

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

出力

1