এই সমস্যায় আমাদের একটি বাইনারি ট্রি দেওয়া আছে এবং একটি নির্দিষ্ট নোড থেকে DFS (Depth First Search) করতে হবে যেখানে সেই নোডকে রুট ধরে DFS করা হবে।
উপরের ট্রিতে ধরি আমাদের নোড F-থেকে DFS করতে হচ্ছে।
এই টিউটোরিয়ালে আমরা কিছু অনন্য পদ্ধতি প্রয়োগ করব যাতে টাইম কমপ্লেক্সিটি উল্লেখযোগ্যভাবে কমে যায় এবং উচ্চ কনস্ট্রেইন্টের জন্যও কোডটি চলে।
পদ্ধতি − এই পদ্ধতিতে আমরা নїв (naive) পথে যাবো না অর্থাৎ প্রতিটি নোডের জন্য আলাদা DFS করবো না কারণ এটি উচ্চ কনস্ট্রেইন্টের জন্য কাজ করবে না (TLE দেবে)। তাই আমরা কিছু অনন্য পদ্ধতি ব্যবহার করব TLE এড়ানোর জন্য।
#include <bits/stdc++.h> using namespace std; #define N 100000 // অ্যাডজেসেন্সি লিস্ট vector<int> v[N]; unordered_map<int, int> mape; // নোডকে তার ইনডেক্সের সাথে ম্যাপ করার জন্য vector<int> a; void dfs(int nodesunder[], int child, int parent){ // DFS ও nodesunder প্রিক্যালকুলেশন a.push_back(child); // ট্রির DFS অর্ডার সংরক্ষণ nodesunder[child] = 1; for (auto it : v[child]) { // সাধারণ DFS if (it != parent) { // সাইকেল এড়ানোর জন্য প্যারেন্ট এড়ানো dfs(nodesunder, it, child); // রিকার্সিভ কল nodesunder[child] += nodesunder[it]; // চাইল্ডের নিচের নোড যোগ করা } } } // সাবট্রির DFS প্রিন্ট করার ফাংশন void printDFS(int node, int nodesunder[]){ int ind = mape[node]; // DFS অ্যারেতে নোডের ইনডেক্স cout << "The DFS of subtree " << node << ": "; // সাবট্রির DFS প্রিন্ট for (int i = ind; i < ind + nodesunder[node]; i++){ // DFS অ্যারেতে নোডের ইনডেক্স থেকে তার সাবট্রির সব নোড প্রিন্ট cout << a[i] << " "; } cout << endl; } void addEdgetoGraph(int x, int y){ // অ্যাডজেসেন্সি লিস্ট মেইনটেইন v[x].push_back(y); v[y].push_back(x); } void mark(){ // প্রতিটি নোডকে DFS অ্যারেতে তার ইনডেক্স দিয়ে মার্ক করা int size = a.size(); for (int i = 0; i < size; i++) { mape[a[i]] = i; } } int main(){ int n = 7; // ট্রির এজ যোগ করা addEdgetoGraph(1, 2); addEdgetoGraph(1, 3); addEdgetoGraph(2, 4); addEdgetoGraph(2, 5); addEdgetoGraph(4, 6); addEdgetoGraph(4, 7); // প্রতিটি নোডের সাবট্রিতে নোড সংখ্যা রাখার অ্যারে int nodesunder[n + 1]; dfs(nodesunder, 1, 0); // nodesunder অ্যারে জেনারেট mark(); // ম্যাপে ইনডেক্স মার্ক করা // কোয়ারী ১ printDFS(2, nodesunder); // কোয়ারী ২ 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 প্রিক্যালকুলেট হলে, আমরা প্রতিটি নোড থেকে শুরু হয়ে তার সাবট্রিতে কতগুলো নোড আছে সেটাও বের করি। তারপর কোয়ারী করার সময় শুধু ওই নোডের স্টার্টিং ইনডেক্স থেকে তার সাবট্রির নোড সংখ্যা পর্যন্ত DFS অ্যারেটি ট্রাভার্স করি।
এই টিউটোরিয়ালে আমরা ট্রির একটি সাবট্রির DFS কোয়ারী সমাধান করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটি সহায়ক পাবেন।
