একটি N-ary গাছ দেওয়া হয়েছে এবং আমাদের এই গাছটি অতিক্রম করার মোট উপায় খুঁজে বের করার দায়িত্ব দেওয়া হয়েছে, উদাহরণস্বরূপ −
উপরের গাছের জন্য, আমাদের আউটপুট হবে 192।
এই সমস্যার জন্য, আমাদের সমন্বয়বিদ্যা সম্পর্কে কিছু জ্ঞান থাকতে হবে। এখন এই সমস্যায়, আমাদের কেবল প্রতিটি পথের জন্য সমস্ত সম্ভাব্য সমন্বয় পরীক্ষা করতে হবে এবং এটি আমাদের উত্তর দেবে৷
সমাধান খোঁজার পদ্ধতি
এই পদ্ধতিতে, আমাদের কেবলমাত্র একটি লেভেল অর্ডার ট্রাভার্সাল করতে হবে এবং প্রতিটি নোডের বাচ্চার সংখ্যা পরীক্ষা করতে হবে এবং তারপরে উত্তরের সাথে তার ফ্যাক্টরিয়াল গুন করতে হবে।
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
char key;
vector<Node *> child;
};
Node *createNode(int key){ // function to initialize a new node
Node *temp = new Node;
temp->key = key;
return temp;
}
long long fact(int n){
if(n <= 1)
return 1;
return n * fact(n-1);
}
int main(){
Node *root = createNode('A');
(root->child).push_back(createNode('B'));
(root->child).push_back(createNode('F'));
(root->child).push_back(createNode('D'));
(root->child).push_back(createNode('E'));
(root->child[2]->child).push_back(createNode('K'));
(root->child[1]->child).push_back(createNode('J'));
(root->child[3]->child).push_back(createNode('G'));
(root->child[0]->child).push_back(createNode('C'));
(root->child[2]->child).push_back(createNode('H'));
(root->child[1]->child).push_back(createNode('I'));
(root->child[2]->child[0]->child).push_back(createNode('N'));
(root->child[2]->child[0]->child).push_back(createNode('M'));
(root->child[1]->child[1]->child).push_back(createNode('L'));
queue<Node*> q;
q.push(root);
long long ans = 1;
while(!q.empty()){
auto z = q.front();
q.pop();
ans *= fact(z -> child.size());
cout << z->child.size() << " ";
for(auto x : z -> child)
q.push(x);
}
cout << ans << "\n";
return 0;
} আউটপুট
4 1 2 2 1 0 0 1 2 0 0 0 0 0 192
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা BFS (ব্রেডথ-ফার্স্ট সার্চ) বা লেভেল অর্ডার ট্রাভার্সাল প্রয়োগ করি এবং প্রতিটি নোডের বাচ্চাদের সংখ্যা পরীক্ষা করি। তারপর, সেই সংখ্যার ফ্যাক্টরিয়ালকে আমাদের উত্তরে গুণ করুন।
উপসংহার
এই টিউটোরিয়ালটি এন-আরি ট্রি কম্বিনেটরিক্স এবং BFS প্রয়োগের মাধ্যমে অতিক্রম করার বিভিন্ন উপায় খুঁজে পেয়েছে। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং আমরা যে সম্পূর্ণ পদ্ধতির সমাধান করেছি তাও শিখেছি।
আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
