इस ट्यूटोरियल में, हम ट्री में पूर्वज-वंशज संबंध के लिए क्वेरी खोजने के प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें एक रूटेड ट्री और Q क्वेरीज प्रदान की जाएंगी। हमारा कार्य क्वेरी में दिए गए दो नोड्स में से एक का दूसरे का पूर्वज है या नहीं, यह पता लगाना है।
उदाहरण
#include <bits/stdc++.h> using namespace std; //DFS का उपयोग करके दिए गए नोड्स के बीच संबंध खोजना void performingDFS(vector<int> g[], int u, int parent, int timeIn[], int timeOut[], int& count) { timeIn[u] = count++; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v != parent) performingDFS(g, v, u, timeIn, timeOut, count); } //नोड को आउट-टाइम निर्दिष्ट करना timeOut[u] = count++; } void processingEdges(int edges[][2], int V, int timeIn[], int timeOut[]) { 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 count = 0; performingDFS(g, 0, -1, timeIn, timeOut, count); } //जांचना कि क्या एक दूसरे का पूर्वज है string whetherAncestor(int u, int v, int timeIn[], int timeOut[]) { bool b = (timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u]); return (b ? "yes" : "no"); } int main() { int edges[][2] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 1, 4 }, { 2, 5 }, }; int E = sizeof(edges) / sizeof(edges[0]); int V = E + 1; int timeIn[V], timeOut[V]; processingEdges(edges, V, timeIn, timeOut); int u = 1; int v = 5; cout << whetherAncestor(u, v, timeIn, timeOut) << endl; return 0; } आउटपुट
no
