C++ 将树添加的边的最大数量,使其保持二分图
目标是通过添加尽可能多的边将一个N节点的树转变为二分图。
请记住,不允许存在自环和多重边,但是可以存在循环。
说明:
解释: 可以添加一条连接节点3和4的边以保持图的二分性。
图中只能添加一条边使其成为二分图。
解释: 即使添加了两个边(3, 4)和(3, 5),图仍然是二部图。
简单方法
问题的基本解决方法如下所述:
树中的每个节点应该被赋予一种颜色,从而形成黑色节点和白色节点之间的连接(树始终是二部图,因此总是存在这样的配置)。
然后,对于每对可行的节点,确定是否可以在它们之间添加一条边。
将上述思想付诸实践,按照下面的步骤进行操作:
- 最初,遍历树,给每个节点赋予黑色或白色,使得每条边连接一个黑色节点和一个白色节点。(所有的树都是二部图。)
- 检查是否可以在每对节点之间添加一条边,通过迭代遍历它们。
- 如果节点的颜色不同且它们之间没有边,则可以添加一条边。所以,增加计数器的值。
- 没有其他方法可以给任何东西添加边。
- 答案是计数器的总值。
上述方法的实现如下。
C++程序:
输出:
- 时间复杂度为 **O(N 2 )。 **
- 辅助空间复杂度为 **O(N 2 )。 **
高效方法
前面的方法中所需的时间可以通过以下观察来减少:
- 假设树起初有B个黑色节点和W个白色节点。因此,从这些节点构建的二分图可以有最多的B*W条边。
- 因此,对于N个节点,可以添加到树中的最大边数为B*W-(N-1) [因为具有N个节点的树有N-1条边]。
按照以下步骤进行操作:
- 首先遍历树,给每个节点分配黑色或白色的颜色,以便每条边连接一个黑色节点和一个白色节点。(所有的树都是二分的。)
- 确定黑色节点和白色节点的数量。
- 根据上述观察的公式确定可以添加的最大边数。
上述方法的实现如下。
C++程序:
输出:
- 时间复杂度将为 O(N) 。
- 辅助空间将为 O(N) 。