Pythonでフォレストを接続するプログラム

隣接リストとしてグラフがあるとします。このグラフは、実際には互いに素なツリーのセットです。森が1本の木になるように、森に一定数のエッジを追加する必要があります。任意の2つのノード間の最長パスの可能な最小距離を返す必要があります。したがって、入力が次のような場合

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

エッジ0−> 5を追加できます。次に、最長のパスは3 −> 1 −> 0 −> 5 −>7または4−> 1 −> 0 −> 5 −>7のいずれかになります。また、方向が逆になっているこれらのパス。したがって、距離4を返します。

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

• 見た：=新しいセット

• dic：=グラフ

• 関数treeDepth（）を定義します。これはノードを取ります。

  • ret：=0

  • 関数dfs1（）を定義します。これはノード、親を取ります。

    • セットにノードを追加します

    • best2：=空の最小ヒープ構造

    • dic [node]のnxtごとに、実行

      • nxtが親と同じでない場合、

        • push（dfs1（nxt、node）+ 1）into best2

      • len（best2）> 2の場合、

        • ヒープからポップ（best2）

      • best2が空の場合、

        • 0を返す

      • ret：=retの最大値、best2のすべての要素の合計

      • best2の最大値を返す

    • dfs1（node、null）

    • retを返す

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

• ret：=0、opt：=新しいリスト、歌う：=0

  • 0からグラフのサイズまでの範囲のノードについては、次のようにします

    • ノードがseenに存在する場合、

      • 次のイテレーションに行く

    • res：=treeDepth（node）

    • 歌う：=歌う最大、解像度

    • optの最後に（res / 2）の天井を挿入します

  • optのサイズが<=1の場合、

    • 歌う

  • mx：=optの最大値

  • 0からoptのサイズまでの範囲のiの場合、実行します

    • opt [i]がmxと同じ場合、

      • opt [i]：=opt [i] − 1

      • ループから出てきます

  • 0からoptのサイズまでの範囲のiの場合、実行します

    • opt [i]：=opt [i] + 1

  • high2：=optからの最大の2つの要素。

  • sum（high2）の最大値を返し、歌う

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

例

import heapq, math
class Solution:
   def solve(self, graph):
      seen = set()
      dic = graph
      def treeDepth(node):
         self.ret = 0
         def dfs1(node, parent):
            seen.add(node)
            best2 = []
            for nxt in dic[node]:
               if nxt != parent:
                  heapq.heappush(best2, dfs1(nxt, node) + 1)
                  if len(best2) > 2:
                     heapq.heappop(best2)
            if not best2:
               return 0
            self.ret = max(self.ret, sum(best2))
            return max(best2)
         dfs1(node, None)
         return self.ret
      ret = 0
      opt = []
      sing = 0
      for node in range(len(graph)):
         if node in seen:
            continue
         res = treeDepth(node)
         sing = max(sing, res)
         opt.append(int(math.ceil(res / 2)))
      if len(opt) <= 1:
         return sing
      mx = max(opt)
      for i in range(len(opt)):
         if opt[i] == mx:
            opt[i] −= 1
            break
         for i in range(len(opt)):
            opt[i] += 1
         high2 = heapq.nlargest(2, opt)
         return max(sum(high2), sing)
ob = Solution()
graph = [
   [1, 2],
   [0,3,4],
   [0],
   [1],
   [1],
   [6,7],
   [5],
   [5]
]
print(ob.solve(graph))

入力

graph = [
   [1, 2],
   [0,3,4],
   [0],
   [1],
   [1],
   [6,7],
   [5],
   [5]
]

出力

4