समस्या विवरण
इस समस्या में, हमें N वर्टेक्स वाला एक ट्री और Q क्वेरीज दी गई हैं जिनमें प्रत्येक में दो मान i और j होते हैं। हमारा कार्य ट्री में पूर्वज-वंशज संबंध के लिए क्वेरी को हल करने का प्रोग्राम बनाना है।
प्रत्येक क्वेरी को हल करने के लिए, हमें जांचना होगा कि नोड i ट्री में नोड j का पूर्वज है या नहीं।
उदाहरण
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Q = 2, query[][] = {{3, 5}, {1, 6}}
आउटपुट
No Yes
व्याख्या
i = 3, j = 5: नोड 3, नोड 5 का पूर्वज नहीं है। NO वापस करें। i = 1, j = 6: नोड 1, नोड 6 का पूर्वज है। 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 not Ancestor For query 2 : is Ancestor
