【C++】木構造を偶数ノードの森（フォレスト）に変換するアルゴリズムを解説

このチュートリアルでは、木構造を「偶数個のノードを持つ木からなる森」に変換するプログラムをC++で実装する方法を解説します。

N個のノードからなる木が与えられます。すべての連結成分（木）のノード数が偶数になるように辺を取り除いたとき、削除できる辺の最大数を求めるのが課題です。

問題のポイント

まず押さえておきたい重要な性質として、木全体のノード数が偶数である場合にのみ、すべての木が偶数ノードになるような森を作ることができます。奇数サイズの木は、どのように分割しても偶数サイズの木だけにすることはできないためです。

解法のアプローチ

この問題は深さ優先探索（DFS）を利用すると効率的に解けます。考え方は以下の通りです。

1. ルート（ノード1）からDFSを開始し、各子部分木に含まれるノード数を再帰的に数えます。
2. ある部分木のノード数が偶数であれば、その部分木を親から切り離すことができるため、削除する辺の数を1つ増やします。
3. ノード数が奇数の場合は、その数を親の部分木に加算して処理を継続します。
4. 最終的にカウントされた値が、削除可能な辺の最大数となります。

C++での実装例

#include<bits/stdc++.h>
#define N 12
using namespace std;
//ルートノードを含む部分木のノード数を返す関数
int depth_search(vector<int> tree[N], int visit[N], int *ans, int node){
    int num = 0, temp = 0;
    //ノードを訪問済みとしてマーク
    visit[node] = 1;
    for (int i = 0; i < tree[node].size(); i++){
        if (visit[tree[node][i]] == 0){
            //子部分木の合計ノード数を求める
            temp = depth_search(tree, visit, ans, tree[node][i]);
            //ノード数が偶数なら、削除する辺の数を1増やす
            (temp%2)?(num += temp):((*ans)++);
        }
    }
    return num+1;
}
//削除する辺の最大数を返す関数
int print_maxedge(vector<int> tree[N], int n){
    int visit[n+2];
    int ans = 0;
    memset(visit, 0, sizeof visit);
    depth_search(tree, visit, &ans, 1);
    return ans;
}
int main(){
    int n = 10;
    vector<int> tree[n+2];
    tree[1].push_back(3);
    tree[3].push_back(1);
    tree[1].push_back(6);
    tree[6].push_back(1);
    tree[1].push_back(2);
    tree[2].push_back(1);
    tree[3].push_back(4);
    tree[4].push_back(3);
    tree[6].push_back(8);
    tree[8].push_back(6);
    tree[2].push_back(7);
    tree[7].push_back(2);
    tree[2].push_back(5);
    tree[5].push_back(2);
    tree[4].push_back(9);
    tree[9].push_back(4);
    tree[4].push_back(10);
    tree[10].push_back(4);
    cout << print_maxedge(tree, n) << endl;
    return 0;
}

出力結果

2

出力の解説

この例では、合計10個のノードを持つ木を入力としています。DFSによって各部分木のノード数を確認すると、偶数サイズの部分木を2箇所で切り離すことができます。そのため、答えは 2 となります。

計算量の評価

• 時間計算量：O(N) — すべてのノードを一度ずつ訪問するだけで完了します。
• 空間計算量：O(N) — 訪問管理用の配列と隣接リスト（グラフ）の保持に、ノード数に比例したメモリを使用します。

まとめ

木を偶数ノードの森に変換する問題は、「部分木のサイズが偶数ならばその辺を削除できる」というシンプルな発想をDFSと組み合わせることで、線形時間O(N)で解くことができます。木構造・再帰・DFSの理解を深めるのに最適な練習問題なので、ぜひ自分でも実装してみてください。