用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与parent不同，则

      • 将(dfs1(nxt, node)+1)压入best2
    • 如果best2的长度>2，则
      • 从heap中弹出best2
    • 如果best2为空，则
      • 返回0
    • ret := 最大值（ret，best2所有元素之和）

    • return best2的最大值

    • dfs1(node, null)

    • return ret

• 从主函数中执行以下步骤-

• ret := 0，opt := 一个新的列表，sing := 0

  • 对于图中的节点范围从0到大小，执行以下操作
    • 如果节点出现在seen中，则

    • 进入下一轮循环

    • res :=treeDepth(node)

    • sing := 最大值（sing，res）

    • 将（res/2）的天花板插入opt列表的末尾

  • 如果opt列表的大小小于等于1，则

    • 返回sing
  • mx :=最大值（opt）

  • 对于opt列表的大小范围从0到大小，执行以下操作

    • 如果opt[i]与mx相同，则

    • 将opt[i] – 1

    • 退出循环

  • 对于opt列表大小的范围从0到大小，执行以下操作

    • 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