এই সমস্যায়, আমাদের একটি অ্যাডজেসেন্সি লিস্ট দেওয়া হয়েছে যা একটি n-এরি ট্রি নির্দেশ করে। আমাদের কাজ হলো n-এরি ট্রিতে জোড় আকারের সাবট্রির সংখ্যা বের করা।
n-এরি ট্রি (N-ary tree) হলো নোডের সংকলন যেটি সাধারণত হায়ারার্কিক্যালি নিচেরভাবে রিপ্রেজেন্ট করা হয়:
ট্রি রুট নোড থেকে শুরু হয়।
ট্রির প্রতিটি নোড তার চাইল্ড নোডগুলোর পয়েন্টারের একটি লিস্ট মেনটেইন করে।
চাইল্ড নোডের সংখ্যা m-এর চেয়ে কম বা সমান।
উদাহরণ দিয়ে সমস্যাটি বোঝা যাক
ইনপুট:
আউটপুট: 4
ব্যাখ্যা:
৭ দিয়ে রুট করা ট্রির জোড় আকার আছে।
২ দিয়ে রুট করা ট্রির জোড় আকার আছে।
০ দিয়ে রুট করা ট্রির জোড় আকার আছে।
৩ দিয়ে রুট করা ট্রির জোড় আকার আছে।
সমাধানের পদ্ধতি
একটি সহজ পদ্ধতি হলো একটি দিয়ে নোডের সব চাইল্ড নোড গণনা করা, যদি জোড় হয় তবে evenTreeCount বাড়ানো। এর জন্য আমরা DFS ব্যবহার করব, এবং দিয়ে নোডের জন্য সাবট্রির দৈর্ঘ্য বের করব।
এটি আমরা ট্রিতে একক ট্রাভার্সাল দিয়ে করতে পারি। প্রতিটি চাইল্ড নোডের সাবট্রির আকার রিকার্সিভলি বের করে সেটি চেক করব এবং যদি জোড় হয় তবে evenTreeCount বাড়াব অন্যথায় ছেড়ে দিব।
সমাধানটি ব্যাখ্যা করে প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int countEventSizeSubTree(vector<int> adj[], int n, int v, int& EvenCount) {
int size = 1;
for (auto ele : adj[v]) {
size += countEventSizeSubTree(adj, n, ele, EvenCount);
}
if (size % 2 == 0)
EvenCount++;
return size;
}
int main() {
int n;
n = 10;
vector<int> adj[n + 1];
adj[7].push_back(2);
adj[7].push_back(9);
adj[2].push_back(0);
adj[2].push_back(1);
adj[9].push_back(3);
adj[3].push_back(8);
adj[0].push_back(5);
int EvenCount = 0;
countEventSizeSubTree(adj, n, 1, EvenCount);
cout << "Even Size SubTree are " << EvenCount;
return 0;
}
আউটপুট
Even Size SubTree are 0
