Python連線森林程式

假設我們有圖作為鄰接表。這個圖實際上是一組不相交的樹。我們必須向森林中新增一定數量的邊，使其成為一棵樹。我們必須返回任意兩個節點之間最長路徑的最小可能距離。因此，如果輸入類似於

則輸出將為4。

我們可以新增邊 0 -> 5。然後，最長路徑可以是 3 -> 1 -> 0 -> 5 -> 7 或 4 -> 1 -> 0 -> 5 -> 7；以及這些路徑的反向方向。因此我們返回距離 4。

為了解決這個問題，我們將遵循以下步驟：

  • seen := 一個新的集合

  • dic := 圖

  • 定義一個函式 treeDepth()。這將接受節點作為引數。

    • ret := 0

    • 定義一個函式 dfs1()。這將接受節點和父節點作為引數。

      • 將節點新增到集合 seen 中

      • best2 := 一個空的最小堆結構

      • 對於 dic[node] 中的每個 nxt，執行：

        • 如果 nxt 不等於父節點，則

          • 將 push(dfs1(nxt, node) + 1) 推入 best2

        • 如果 len(best2) > 2，則

          • 從堆 (best2) 中彈出元素

        • 如果 best2 為空，則

          • 返回 0

        • ret := ret，best2所有元素之和的最大值

        • 返回 best2 的最大值

      • dfs1(node, null)

      • 返回 ret

  • 從主方法執行以下操作：

  • ret := 0, opt := 一個新的列表, sing := 0

    • 對於範圍從 0 到圖大小的每個節點，執行：

      • 如果節點存在於 seen 中，則

        • 跳過本次迭代

      • res := treeDepth(node)

      • sing := sing 和 res 的最大值

      • 將 ceil(res / 2) 插入到 opt 的末尾

    • 如果 opt 的大小 <= 1，則

      • 返回 sing

    • mx := opt 的最大值

    • 對於範圍從 0 到 opt 大小的每個 i，執行：

      • 如果 opt[i] 等於 mx，則

        • opt[i] := opt[i] - 1

        • 跳出迴圈

    • 對於範圍從 0 到 opt 大小的每個 i，執行：

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

    • high2 := opt 中最大的兩個元素。

    • 返回 sum(high2) 和 sing 的最大值

讓我們看看下面的實現，以便更好地理解：

示例

線上演示

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

更新於：2020年12月15日

瀏覽量：150

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告