用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
-
从主函数中执行以下步骤-
-
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的最大值
- 对于图中的节点范围从0到大小,执行以下操作
让我们看下面的实现,以便更好地理解。