คำชี้แจงปัญหา
จากต้นไม้ที่ไม่มีทิศทางซึ่งมีจุดยอดเป็นคู่ เราจำเป็นต้องลบจำนวนขอบสูงสุดออกจากต้นไม้นี้ เพื่อให้องค์ประกอบที่เชื่อมต่อกันของฟอเรสต์ผลลัพธ์มีจำนวนจุดยอดเท่ากัน
ตัวอย่าง
ในแผนภูมิต้นไม้ที่แสดงด้านบนนี้ เราสามารถลบได้สูงสุด 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
