समस्या कथन
एक अनडायरेक्टेड ट्री दिया गया है जिसमें सम संख्या में वर्टेक्स हैं। हमें इस ट्री से अधिकतम संख्या में एज हटाने की आवश्यकता है ताकि परिणामी फॉरेस्ट के प्रत्येक कनेक्टेड कंपोनेंट में सम संख्या में वर्टेक्स हों।
उदाहरण
ऊपर दिखाए गए ट्री में, हम अधिकतम 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
