C++でフォレストを均一にするためのツリーからの最大エッジ除去

問題の説明

頂点の数が偶数である無向ツリーの場合、結果のフォレストの連結成分ごとに頂点の数が偶数になるように、このツリーから最大数のエッジを削除する必要があります。

例

上に示したツリーでは、接続された各コンポーネントが偶数の頂点を持つように、赤で示された最大2つのエッジ0-2と0-4を削除できます。

アルゴリズム

• ツリーが接続されているときに、任意の開始ノードからDFSを実行します
• 現在のノードの下にルート化されたサブツリー内のノードの数を0として初期化します
• 現在のノードのすべてのサブツリーに対して再帰的にフォローする-
  • 現在のサブツリーのサイズが偶数の場合、サブツリーを切断できるため、結果を1ずつ増やします
  • それ以外の場合は、現在のサブツリー内のノードの数を現在の数に追加します

例

例を見てみましょう-

#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