এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম নিয়ে আলোচনা করব যা একটি ট্রিকে জোড় নোডের ফরেস্টে (forest of even nodes) রূপান্তর করে।
এখানে আমাদের N নোডের একটি বাইনারি ট্রি দেওয়া থাকবে। আমাদের কাজ হলো সর্বোচ্চ কতগুলো এজ সরিয়ে জোড় নোডের ফরেস্ট তৈরি করা যায় তা বের করা।
উদাহরণ
#include<bits/stdc++.h> #define N 12 using namespace std; //সাবট্রির নোড সংখ্যা রিটার্ন করে //যার রুট নোড int depth_search(vector<int> tree[N], int visit[N], int *ans, int node){ int num = 0, temp = 0; //নোডগুলো ভিজিটেড চিহ্নিত করা visit[node] = 1; for (int i = 0; i < tree[node].size(); i++){ if (visit[tree[node][i]] == 0){ //সাব সাবট্রির মোট নোড বের করা temp = depth_search(tree, visit, ans, tree[node][i]); //যদি নোডগুলো জোড় হয়, তবে সরানো এজের সংখ্যা ১ বাড়ানো (temp%2)?(num += temp):((*ans)++); } } return num+1; } //সর্বোচ্চ সরানোয়োগ্য এজের সংখ্যা রিটার্ন করা int print_maxedge(vector<int> tree[N], int n){ int visit[n+2]; int ans = 0; memset(visit, 0, sizeof visit); depth_search(tree, visit, &ans, 1); return ans; } int main(){ int n = 10; vector<int> tree[n+2]; tree[1].push_back(3); tree[3].push_back(1); tree[1].push_back(6); tree[6].push_back(1); tree[1].push_back(2); tree[2].push_back(1); tree[3].push_back(4); tree[4].push_back(3); tree[6].push_back(8); tree[8].push_back(6); tree[2].push_back(7); tree[7].push_back(2); tree[2].push_back(5); tree[5].push_back(2); tree[4].push_back(9); tree[9].push_back(4); tree[4].push_back(10); tree[10].push_back(4); cout << print_maxedge(tree, n) << endl; return 0; }আউটপুট
2
