Tuyên bố vấn đề
Cho một cây vô hướng có số đỉnh chẵn, chúng ta cần loại bỏ số cạnh tối đa khỏi cây này sao cho mỗi thành phần được kết nối của rừng kết quả có số đỉnh chẵn.
Ví dụ
Trong cây được hiển thị ở trên, chúng ta có thể loại bỏ tối đa 2 cạnh 0-2 và 0-4 được hiển thị bằng màu đỏ sao cho mỗi thành phần được kết nối sẽ có số đỉnh chẵn.
Thuật toán
- Thực hiện DFS từ bất kỳ nút bắt đầu nào khi cây được kết nối
- Khởi tạo số lượng nút trong cây con bắt nguồn từ nút hiện tại là 0
- Thực hiện theo đệ quy cho mọi cây con của nút hiện tại -
- Nếu kích thước của cây con hiện tại là chẵn, kết quả tăng lên 1 vì chúng tôi có thể ngắt kết nối cây con
- Khác thêm số lượng nút trong cây con hiện tại vào số lượng hiện tại
Ví dụ
Bây giờ chúng ta hãy xem một ví dụ -
#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;
} Đầu ra
Answer = 2