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