C++ এ n-আরি ট্রিতে ইভেন সাইজ সাবট্রি

এই সমস্যায়, আমাদের একটি সংলগ্ন তালিকা দেওয়া হয়েছে যা একটি n-ary গাছকে বোঝায়। আমাদের কাজ হল এন-আরি ট্রিতে সম আকারের সাবট্রির সংখ্যা খুঁজে বের করা।

N-ary গাছ নোডের একটি সংগ্রহ হিসাবে সংজ্ঞায়িত করা হয় যা সাধারণত নিম্নোক্ত পদ্ধতিতে অনুক্রমিকভাবে উপস্থাপিত হয়৷

গাছটি রুট নোডে শুরু হয়৷৷

গাছের প্রতিটি নোড তার চাইল্ড নোডের পয়েন্টারগুলির একটি তালিকা বজায় রাখে৷৷

চাইল্ড নোডের সংখ্যা m এর থেকে কম বা সমান।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট:

আউটপুট: 4

ব্যাখ্যা:

7 দিয়ে শিকড়যুক্ত গাছের সমান আকার রয়েছে।
2 দিয়ে শিকড়যুক্ত গাছের সমান আকার রয়েছে।
0 দিয়ে শিকড়যুক্ত গাছের সমান আকার রয়েছে।
3 দিয়ে শিকড়যুক্ত গাছের সমান আকার রয়েছে।

সমাধান পদ্ধতি -

একটি সহজ পদ্ধতি হল প্রদত্ত নোডের জন্য সমস্ত চাইল্ড নোড গণনা করা, যদি এটি এমনকি EvenTreeCount বৃদ্ধি করে। এর জন্য আমরা ডিএফএস ব্যবহার করব, এবং প্রদত্ত নোডের জন্য সাবট্রির দৈর্ঘ্য খুঁজে বের করব।

আমরা গাছে একটি একক ট্রাভার্সাল ব্যবহার করে এটি করতে পারি। বারবার প্রতিটি চাইল্ড নোডের সাবট্রির সাইজ খুঁজে বের করে তারপর সাইজ চেক করুন এবং যদি সমান হয়, তাহলে EvenTreeCount বাড়ান অন্যথায় ছেড়ে দিন।

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int countEventSizeSubTree(vector<int> adj[], int n, int v, int&amp; 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