C++で2部グラフを維持するためにツリーに追加されるエッジの最大数

問題の説明

ツリーは常に2部グラフです。これは、レベルが交互になっている2つの互いに素なセットにいつでも分割できるためです。

つまり、交互のレベルが同じ色になるように、常に2つの色で色付けします。タスクは、最大数を計算することです。 2部グラフのままにするためにツリーに追加できるエッジの数。

例

ツリーエッジは、次のように頂点ペアで表されます-

{1、2}

{1、3}

{2、4}

{3、5}次に、2部グラフを維持するためにさらに2つのエッジが必要です

• 彩色グラフでは、2つの異なるセットからのグラフ{1、4、5}と{2、3}。以来、1は2と3の両方から接続されています
• エッジ4と5が残っています。4はすでに2と5から3に接続されているため、残りのオプションは{4、3}と{5、2}のみです。

アルゴリズム

• グラフの単純なDFSまたはBFSトラバーサルを実行し、2色で色付けします
• カラーリングは、2色でカラーリングされたノードの数も追跡します。 2つのカウントをcount_color0とcount_color1とします
• これで、2部グラフが持つことができる最大エッジは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