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

开启你的职业生涯

完成课程获得认证

开始学习
广告