इस समस्या में, हमें एक एन वर्टेक्स ट्री और क्यू प्रश्न दिए गए हैं जिनमें से प्रत्येक में दो मान 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.
समाधान दृष्टिकोण
समस्या का समाधान ट्री ट्रैवर्सिंग तकनीक का उपयोग कर रहा है जो डीएफएस (गहराई पहले खोज) है। हम 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