Pythonで特定のエッジを含む一意のパスの数をカウントするプログラム

（u、v）の形式のエッジのリストがあり、これらがツリーを表しているとします。エッジごとに、入力で指定されたのと同じ順序で、そのエッジを含む一意のパスの総数を見つける必要があります。

したがって、入力がエッジのような場合=[[0、1]、[0、2]、[1、3]、[1、4]]

その場合、出力は[6、4、4、4]になります。

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

• adj：=指定されたエッジからの隣接リスト

• count：=空のマップ

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

• count [x]：=1

• adj [x]のnbごとに、実行

  • nbが親と同じ場合、

    • ループから出てきます

  • count [x]：=count [x] + dfs（nb、x）

• リターンカウント[x]

• メインの方法から、次のようにします-

• dfs（0、-1）

• ans：=新しいリスト

• エッジの各エッジ（a、b）について、実行します

  • x：=count[a]とcount[b]

    の最小値

  • ansの最後に（x *（count [0]-x））を挿入します

• ansを返す

例

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

from collections import defaultdict
class Solution:
   def solve(self, edges):
      adj = defaultdict(list)
      for a, b in edges:
         adj[a].append(b)
         adj[b].append(a)
      count = defaultdict(int)
      def dfs(x, parent):
         count[x] = 1
         for nb in adj[x]:
            if nb == parent:
               continue
            count[x] += dfs(nb, x)
         return count[x]
      dfs(0, -1)
      ans = []
      for a, b in edges:
         x = min(count[a], count[b])
         ans.append(x * (count[0] - x))
      return ans
ob = Solution()
edges = [
   [0, 1],
   [0, 2],
   [1, 3],
   [1, 4]
]
print(ob.solve(edges))

入力

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

出力

[6, 4, 4, 4]