要添加到树中以使其在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_color0 x count_color1

• 我们还知道具有n个节点的树具有n-1边

• 所以我们的答案是count_color0 x count_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