এই সমস্যায় আমাদের একটি বাইনারি ট্রি দেওয়া হয়েছে এবং আমাদের একটি নির্দিষ্ট নোড থেকে dfs করতে হবে যেখানে আমরা প্রদত্ত নোডটিকে রুট হিসাবে ধরে নিই এবং এটি থেকে dfs সম্পাদন করি৷
উপরের গাছে ধরুন আমাদের নোড F
থেকে DFS করতে হবেএই টিউটোরিয়ালে আমরা কিছু অপ্রচলিত পদ্ধতি প্রয়োগ করতে যাচ্ছি যাতে এটি আমাদের সময়ের জটিলতাকে উল্লেখযোগ্যভাবে হ্রাস করবে এবং এইভাবে আমরা উচ্চতর সীমাবদ্ধতার জন্যও এই কোডটি চালাতে সক্ষম হব।
পন্থা − এই পদ্ধতিতে আমরা কেবল সরল পথে যেতে যাচ্ছি না, যেখানে আমরা প্রতিটি নোডের জন্য কেবল dfs প্রয়োগ করি কারণ এটি উচ্চতর সীমাবদ্ধতার জন্য কাজ করবে না তাই আমরা TLE পাওয়া এড়াতে কিছু অপ্রচলিত পদ্ধতি ব্যবহার করার চেষ্টা করি।
#include <bits/stdc++.h>
using namespace std;
#define N 100000
// Adjacency list to store the
// tree nodes connections
vector<int> v[N];
unordered_map<int, int> mape; // will be used for associating the node with it's index
vector<int> a;
void dfs(int nodesunder[], int child, int parent){ // function for dfs and precalculation our nodesunder
a.push_back(child); // storing the dfs of our tree
// nodesunder of child subtree
nodesunder[child] = 1;
for (auto it : v[child]) { // performing normal dfs
if (it != parent) { // as we the child can climb up to
//it's parent so we are trying to avoid that as it will become a cycle
dfs(nodesunder, it, child); // recursive call
nodesunder[child] += nodesunder[it]; // storing incrementing the nodesunder
//by the number of nodes under it's children
}
}
}
// Function to print the DFS of subtree of node
void printDFS(int node, int nodesunder[]){
int ind = mape[node]; // index of our node in the dfs array
cout << "The DFS of subtree " << node << ": ";
// print the DFS of subtree
for (int i = ind; i < ind + nodesunder[node]; i++){ // going through dfs array and then
//printing all the nodes under our given node
cout << a[i] << " ";
}
cout << endl;
}
void addEdgetoGraph(int x, int y){ // for maintaining adjacency list
v[x].push_back(y);
v[y].push_back(x);
}
void mark(){ // marking each node with it's index in dfs array
int size = a.size();
// marks the index
for (int i = 0; i < size; i++) {
mape[a[i]] = i;
}
}
int main(){
int n = 7;
// add edges of a tree
addEdgetoGraph(1, 2);
addEdgetoGraph(1, 3);
addEdgetoGraph(2, 4);
addEdgetoGraph(2, 5);
addEdgetoGraph(4, 6);
addEdgetoGraph(4, 7);
// array to store the nodes present under of subtree
// of every node in a tree
int nodesunder[n + 1];
dfs(nodesunder, 1, 0); // generating our nodesunder array
mark(); // marking the indices in map
// Query 1
printDFS(2, nodesunder);
// Query 2
printDFS(4, nodesunder);
return 0;
} আউটপুট
The DFS of subtree 2: 2 4 6 7 5 The DFS of subtree 4: 4 6 7
কোড বোঝা
এই পদ্ধতিতে আমরা dfs-এর ক্রম পূর্ব গণনা করছি এবং এখন এটি একটি ভেক্টরে সংরক্ষণ করছি যখন আমরা dfs-এর পূর্বনির্ধারণ করেছি তখন আমরা প্রতিটি নোড থেকে শুরু করে প্রতিটি সাবট্রির নীচে উপস্থিত নোডগুলিও গণনা করি এবং তারপরে আমরা কেবল নোডের প্রারম্ভিক সূচকটি সকলের কাছে অতিক্রম করি। এর সাবট্রির ভিতরে উপস্থিত নোডের সংখ্যা।
উপসংহার
এই টিউটোরিয়ালে, আমরা একটি গাছের সাবট্রির ডিএফএস-এর জন্য প্রশ্নগুলি সমাধান করার জন্য একটি সমস্যার সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি।
আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আশা করি আপনি এই নিবন্ধটি সহায়ক বলে মনে করেন৷
