C++で2部グラフを維持したまま木に追加できる最大の辺数を求める方法

問題の概要

木（ツリー）は常に2部グラフ（バイパータイトグラフ）です。これは、交互のレベルごとに2つの互いに素な集合へ分割できるためです。

言い換えると、2色を使って交互のレベルが同じ色になるように塗り分けることができます。この問題のタスクは、木が2部グラフであり続けるという条件を満たしたまま、追加できる辺の最大本数を計算することです。

例

木の辺が次の頂点ペアとして与えられているとします。

{1, 2}
{1, 3}
{2, 4}
{3, 5}

この場合、2部グラフを維持するためにさらに2本の辺を追加できます。

• グラフを2色で塗り分けると、{1, 4, 5} と {2, 3} が異なる2つの集合に分かれます。これは、頂点1が頂点2と頂点3の両方に接続されているためです。
• 次に、頂点4と頂点5に注目します。頂点4はすでに頂点2に、頂点5はすでに頂点3に接続されているため、追加できる残りの選択肢は {4, 3} と {5, 2} の2本のみです。

アルゴリズム

• DFS（深さ優先探索）またはBFS（幅優先探索）でグラフを走査し、2色で塗り分けます。
• 塗り分けと同時に、各色で塗られたノードの数を記録します。2つのカウントを count_color0 と count_color1 とします。
• 2部グラフが持ちうる最大の辺数は count_color0 × count_color1 であることがわかります。
• また、n個のノードを持つ木は必ず n-1 本の辺を持つことも既知です。
• したがって、答えは count_color0 × count_color1 − (n-1) となります。

実装例（C++）

#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