এই সমস্যায়, আমাদেরকে একটি N ভার্টেক্স ট্রি এবং Q প্রশ্ন দেওয়া হয়েছে যার প্রতিটিতে দুটি মান i এবং j রয়েছে। আমাদের কাজ হল একটি গাছে পূর্বপুরুষ-বংশের সম্পর্কের জন্য একটি প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা৷
প্রতিটি প্রশ্নের সমাধান করার জন্য, আমাদের পরীক্ষা করতে হবে যে নোড i গাছে নোড j এর পূর্বপুরুষ কিনা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
Q = 2, query[][] = {{3, 5}, {1, 6}} আউটপুট
No Yes
ব্যাখ্যা
i = 3, j = 5: The node 3 is not the ancestor of node 5. Return NO. i = 1, j = 6: The node 1 is the ancestor of node 6. Return YES.
সমাধান পদ্ধতি
সমস্যার একটি সমাধান হল ট্রি ট্রাভার্সিং কৌশল ব্যবহার করা যা DFS (গভীরতার প্রথম অনুসন্ধান)। আমরা ith নোড থেকে ট্র্যাভার্স করব এবং এর সমস্ত বংশধরদের কাছে করব এবং তারপরে jth নোডটি এর বংশধর কিনা তা পরীক্ষা করব। সমস্যা সমাধানের একটি কার্যকর উপায় হল প্রতিটি নোডের টাইম-ইন এবং টাইম-আউট খুঁজে বের করা। এবং তারা পূর্বপুরুষ-বংশের সম্পর্ক ভাগ করে কিনা তা পরীক্ষা করে দেখুন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void depthFirstSearch(vector<int> g[], int u, int parent, int entTime[], int exitTime[], int& cnt){
entTime[u] = cnt++;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v != parent) depthFirstSearch(g, v, u, entTime, exitTime, cnt);
}
exitTime[u] = cnt++;
}
void calcTimeInAndOut(int edges[][2], int V, int entTime[], int exitTime[]){
vector<int> g[V];
for (int i = 0; i < V - 1; i++) {
int u = edges[i][0];
int v = edges[i][1];
g[u].push_back(v);
g[v].push_back(u);
}
int cnt = 0; depthFirstSearch(g, 0, -1, entTime, exitTime, cnt);
}
int main(){
int edges[][2] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 1, 4 }, { 4, 5 }, { 5, 6 }, { 5, 7 }};
int E = sizeof(edges) / sizeof(edges[0]);
int V = E + 1;
int Q = 2;
int query[Q][2] = {{3, 5}, {1, 6}};
int entTime[V], exitTime[V];
calcTimeInAndOut(edges, V, entTime, exitTime);
for(int i = 0; i < Q; i++){
cout<<"For query "<<(i+1)<<" : "; (entTime[query[i][0]] <= entTime[query[i][1]] && exitTime[query[i][0]] <= exitTime[query[i][1]])? cout<<"is Ancestor\n":cout<<"is not Ancestor\n";
}
return 0;
} আউটপুট
For query 1 : is Ancestor For query 2 : is not Ancestor
