এই সমস্যায়, আমাদেরকে N আকারের একটি গাছ, V এবং k গাছের একটি নোড দেওয়া হয়েছে। আমাদের কাজ হল একটি গাছের মধ্যে একটি প্রদত্ত সাবট্রির ডিএফএস ট্রাভার্সালে Kth নোডটি সন্ধান করা .
বৃক্ষের DFS ট্র্যাভার্সালে আমাদের kth নোডটি খুঁজে বের করতে হবে V vertex থেকে শুরু করে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট:
V =2, k =3
আউটপুট:4
ব্যাখ্যা −
The series is {1, 2, 3, 5, 6, 7}
The 4th element is 5. সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল V নোডের DFS ট্রাভার্সাল খুঁজে বের করা এবং এর থেকে kth মান প্রিন্ট করা।
এর জন্য, আমরা গাছের ডিএফএস ট্রাভার্সাল করি এবং এটি একটি ভেক্টরে সংরক্ষণ করি। এই ভেক্টরে, আমরা Vstart-এর মান খুঁজে পাব এবং Vend গাছের DFS ট্রাভার্সালের শুরু এবং শেষ চিহ্নিত করা। তারপর এই পরিসরে k-th মানটি খুঁজুন এবং সম্ভব হলে এটি মুদ্রণ করুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n;
vector<int> tree[N];
int currentIdx;
vector<int> startIdx,endIdx;
vector<int> dfsTraversalVector;
void insertEdge(int u, int v){
tree[u].push_back(v);
tree[v].push_back(u);
}
void findDfsTraversal(int ch, int par){
dfsTraversalVector[currentIdx] = ch;
startIdx[ch] = currentIdx++;
for (auto c : tree[ch]) {
if (c != par)
findDfsTraversal(c, ch);
}
endIdx[ch] = currentIdx - 1;
}
int findKNodeDfsV(int v, int k){
k = k + (startIdx[v] - 1);
if (k <= endIdx[v])
return dfsTraversalVector[k];
return -1;
}
int main(){
n = 9;
insertEdge(5, 8);
insertEdge(5, 2);
insertEdge(5, 10);
insertEdge(5, 3);
insertEdge(2, 6);
insertEdge(2, 1);
insertEdge(3, 9);
insertEdge(6, 1);
insertEdge(9, 7);
startIdx.resize(n);
endIdx.resize(n);
dfsTraversalVector.resize(n);
findDfsTraversal(5, 0);
int v = 2,
k = 4;
cout<<k<<"-th node in DFS traversal of node "<<v<<" is "<<findKNodeDfsV(v, k);
return 0;
} আউটপুট
4-th node in DFS traversal of node 2 is 1
