要添加到树中以使其在C ++中保持Bipartite图的最大边数
问题陈述
一棵树总是二等图，因为我们总是可以分成两个具有交替级别的不相交集。
换句话说，我们总是用两种颜色对其进行着色，以使备用色阶具有相同的颜色。任务是计算最大编号。可以添加到树中的边的数量，以便保留为二部图。
示例
树边以顶点对表示，如下所示-
{1，2}
{1，3}
{2，4}
{3，5}然后我们需要2个更多的边来保持它的二部图
在着色图中，来自两个不同集合的图{1，4，5}和{2，3}。因为1和2和3都相连
我们只剩下边4和5。由于4已连接到2和5至3。仅剩下的选项是{4，3}和{5，2}
算法
对图形进行简单的DFS或BFS遍历，并用两种颜色对其进行着色
同时着色还跟踪用两种颜色着色的节点数。设两个计数为count_color0和count_color1
现在我们知道二部图可以具有的最大边数是count_color0xcount_color1
我们还知道具有n个节点的树具有n-1边
所以我们的答案是count_color0xcount_color1–(n-1)
示例
#include <bits/stdc++.h>
using namespace std;
long long count_color[2];
void dfs(vector<int> graph[], int node, int parent, int color) {
++count_color[color];
for (int i = 0; i < graph[node].size(); ++i) {
if (graph[node][i] != parent) {
dfs(graph, graph[node][i], node, !color);
}
}
}
int getMaxEdges(vector<int> graph[], int n) {
dfs(graph, 1, 0, 0);
return count_color[0] * count_color[1] - (n - 1);
}
int main() {
int n = 5;
vector<int> graph[n + 1];
graph[1].push_back(2);
graph[1].push_back(3);
graph[2].push_back(4);
graph[3].push_back(5);
cout << "Maximum edges = " << getMaxEdges(graph, n) << endl;
return 0;
}输出结果
当您编译并执行上述程序时。它产生以下输出-
Maximum edges = 2