सी ++ में एक पेड़ में पूर्वजों-वंशज संबंधों के लिए प्रश्न

इस ट्यूटोरियल में, हम एक पेड़ में पूर्वज-वंश संबंध के लिए क्वेरी खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।

इसके लिए हमें एक रूटेड ट्री और क्यू प्रश्न प्रदान किए जाएंगे। हमारा काम यह पता लगाना है कि क्वेरी में दिए गए दो मूल दूसरे के पूर्वज हैं या नहीं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
//using DFS to find the relation between
//given nodes
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);
   }
   //assigning out-time to a node
   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);
}
//checking if one is ancestor of another
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