C++で木構造から辺を削除し、全ての連結成分が偶数頂点となる森を作る最大削除数を求める

問題概要

頂点数が偶数である無向木（ツリー）が与えられます。この木からできるだけ多くの辺を取り除き、削除後の森（フォレスト）を構成する各連結成分の頂点数がすべて偶数になるようにします。求めるのは、削除できる辺の最大本数です。

例

上図の木では、赤色で示した 0–2 と 0–4 の2本の辺を削除すると、各連結成分の頂点数がすべて偶数になります。これがこの木における削除可能な辺の最大本数です。

考えるポイント

木全体の頂点数が偶数であるため、サイズが奇数の部分木は必ず偶数個存在し、それらは最終的にどこかで結合して偶数サイズの成分を形成します。つまり、DFSで部分木のノード数を数え、そのサイズが偶数になった時点で親との間の辺を切り離せばよいというのがこの問題の鍵となります。

アルゴリズム

• 木は連結グラフなので、任意のノードを起点として DFS（深さ優先探索）を行う
• 現在のノードを根とする部分木のノード数カウントを 0 で初期化する
• 現在のノードの子部分木ごとに再帰的に以下を実行する
  • その部分木のサイズが偶数なら、切り離すことができるため result を 1 増やす
  • そうでなければ（奇数なら）、その部分木のノード数を現在のカウントに加算する

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int dfs(vector<int> g[], int u, bool visit[], int& res) {
    visit[u] = true;
    int currComponentNode = 0;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!visit[v]) {
            int subtreeNodeCount = dfs(g, v, visit, res);
            if (subtreeNodeCount % 2 == 0)
                res++;
            else
                currComponentNode += subtreeNodeCount;
        }
    }
    return (currComponentNode + 1);
}
int maxEdgeRemovalToMakeForestEven(vector<int> g[], int N) {
    bool visit[N + 1];
    for (int i = 0; i <= N; i++)
        visit[i] = false;
    int res = 0;
    dfs(g, 0, visit, res);
    return res;
}
void addEdge(vector<int> g[], int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}
int main() {
    int edges[][2] = {{0, 2}, {0, 1}, {0, 4}, {2, 3}, {4, 5}, {5, 6}, {5, 7}};
    int N = sizeof(edges)/sizeof(edges[0]); vector<int> g[N + 1];
    for (int i = 0; i < N; i++)
        addEdge(g, edges[i][0], edges[i][1]);
    cout << "Answer = " << maxEdgeRemovalToMakeForestEven(g, N) << endl;
    return 0;
}

出力結果

Answer = 2

計算量について

このアルゴリズムは木の各ノードを1回ずつ訪問するため、時間計算量は O(N)、計算量も頂点数 N に比例し、非常に効率的です。DFSによる部分木サイズの集計だけで答えが求まるため、追加のデータ構造は不要です。