Loại bỏ tối đa cạnh từ cây để thành rừng các thành phần chẵn trong C++

Đề bài

Cho cây vô hướng có số đỉnh chẵn. Loại bỏ nhiều cạnh nhất có thể sao cho mỗi thành phần liên thông của rừng kết quả có số đỉnh chẵn.

Ví dụ: Cây cho trước, có thể loại bỏ 2 cạnh (0-2 và 0-4) để các thành phần đều có số đỉnh chẵn.

Thuật toán (DFS)

1. DFS từ nút bất kỳ (cây liên thông).
2. Đếm số đỉnh của cây con gốc tại nút hiện tại.
3. Với mỗi cây con: nếu kích thước chẵn → tăng kết quả (có thể cắt cạnh nối), nếu lẻ → cộng vào kích thước thành phần hiện tại.

Ví dụ minh họa (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 v : g[u]) {
        if (!visit[v]) {
            int subtreeNodeCount = dfs(g, v, visit, res);
            if (subtreeNodeCount % 2 == 0) res++;
            else currComponentNode += subtreeNodeCount;
        }
    }
    return currComponentNode + 1; // +1 cho nút hiện tại
}

int maxEdgeRemovalToMakeForestEven(vector<int> g[], int N) {
    bool visit[N + 1] = {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 (auto& e : edges) addEdge(g, e[0], e[1]);
    cout << "So canh co the loai bo = " << maxEdgeRemovalToMakeForestEven(g, N) << endl;
    return 0;
}

Kết quả

So canh co the loai bo = 2