การลบ Edge สูงสุดจาก Tree เพื่อทำ Even Forest ใน C++

โจทย์

ได้รับ Undirected Tree ที่มีจำนวนโหนดเป็นเลขคู่ ต้องการลบ Edge จำนวนมากที่สุดจาก Tree นี้ เพื่อให้แต่ละ Connected Component ของ Forest ที่ได้ มีจำนวนโหนดเป็นเลขคู่

ตัวอย่าง

ในต้นไม้ด้านบน สามารถลบ Edge ได้สูงสุด 2 Edge คือ 0-2 และ 0-4 (สีแดง) ทำให้แต่ละ Component มีโหนดเป็นเลขคู่

อัลกอริทึม

• ทำ DFS จากโหนดเริ่มต้นใดก็ได้ (เพราะ Tree เชื่อมต่อกัน)
• เริ่มต้นนับโหนดใน Subtree ที่รากอยู่ที่โหนดปัจจุบันเป็น 0
• ทำแบบ Recursive สำหรับทุก Subtree ของโหนดปัจจุบัน:
  • ถ้าขนาด Subtree ปัจจุบันเป็นเลขคู่ เพิ่มผลลัพธ์ 1 (เพราะสามารถตัด Edge ได้)
  • มิฉะนั้น บวกจำนวนโหนดใน Subtree ปัจจุบันเข้าไปในนับปัจจุบัน

ตัวอย่างโค้ด

#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