সমস্যা বিবৃতি
একটি অনির্দেশিত বৃক্ষের প্রদত্ত যেটিতে জোড় সংখ্যার শীর্ষ রয়েছে, আমাদের এই গাছ থেকে সর্বাধিক সংখ্যক প্রান্ত অপসারণ করতে হবে যাতে ফলস্বরূপ বনের প্রতিটি সংযুক্ত উপাদানের সমান সংখ্যক শীর্ষবিন্দু থাকে৷
উদাহরণ
উপরে দেখানো ট্রিতে, আমরা লাল রঙে দেখানো সর্বাধিক 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
