ট্রিয়ে নির্দিষ্ট সাবট্রির DFS ট্রাভার্সালে k-তম নোড বের করা (C++)

সমস্যা বিবরণ

একটি ট্রি (সাইজ N), একটি নোড V এবং k দেওয়া আছে। আমাদের কাজ হল V নোডকে রুট ধরে তার সাবট্রির DFS ট্রাভার্সালে k-তম নোড বের করা।

উদাহরণ

ট্রি (চিত্র), V=2, k=3 → আউটপুট: 4

সমাধানের পদ্ধতি

পুরো ট্রির DFS ট্রাভার্সাল ভেক্টরে সংরক্ষণ করা। প্রতিটি নোডের জন্য তার সাবট্রির DFS-এ শুরু ও শেষ সূচক (startIdx, endIdx) রেখে k-তম উপাদান O(1)-এ বের করা।

প্রোগ্রাম উদাহরণ

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

const int N=100005;
vector<int> tree[N], startIdx, endIdx, dfsOrder;
int curIdx=0;

void addEdge(int u,int v){ tree[u].push_back(v); tree[v].push_back(u); }

void dfs(int u,int p){
    dfsOrder[curIdx]=u;
    startIdx[u]=curIdx++;
    for(int v:tree[u]) if(v!=p) dfs(v,u);
    endIdx[u]=curIdx-1;
}

int kthNodeInDFS(int v,int k){
    k = k + startIdx[v] - 1;
    if(k <= endIdx[v]) return dfsOrder[k];
    return -1;
}

int main(){
    int n=9;
    addEdge(5,8); addEdge(5,2); addEdge(5,10); addEdge(5,3);
    addEdge(2,6); addEdge(2,1); addEdge(3,9); addEdge(6,1); addEdge(9,7);
    startIdx.resize(n); endIdx.resize(n); dfsOrder.resize(n);
    dfs(5,0);
    cout << kthNodeInDFS(2,4); // 1
    return 0;
}