সমস্যা বিবরণ
একটি অনির্দেশিত ট্রি দেওয়া আছে যাতে কোড়া সংখ্যক ভের্টেক্স আছে। আমাদের এই ট্রি থেকে সর্বোচ্চ সংখ্যক এজ সরাতে হবে যাতে ফলাফলস্বরূপ ফরেস্টের প্রতিটি সংযুক্ত কম্পোনেন্টে কোড়া সংখ্যক ভের্টেক্স থাকে।
উদাহরণ
উপরোক্ত ট্রিতে, আমরা সর্বোচ্চ ২টি এজ 0-2 এবং 0-4 (লাল রঙে দেখানো) সরাতে পারি যাতে প্রতিটি সংযুক্ত কম্পোনেন্টে কোড়া সংখ্যক ভের্টেক্স থাকে।
অ্যালগরিদম
- যেকোনো স্টার্টিং নোড থেকে DFS করুন কারণ ট্রি সংযুক্ত।
- কারেন্ট নোডের অধীনে রুট করা সাবট্রির নোড সংখ্যা ০ দিয়ে আরম্ভ করুন।
- কারেন্ট নোডের প্রতিটি সাবট্রির জন্য রিকার্সিভভাবে নিচের কাজ করুন:
- যতি কারেন্ট সাবট্রির আকার কোড়া হয়, রেজাল্ট ১ বাড়ান কারণ সাবট্রিটি ডিসকানেক্ট করা সম্ভব।
- অন্যথায় কারেন্ট সাবট্রির নোড সংখ্যা কারেন্ট কাউন্টে যোগ করুন।
উদাহরণ
#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
