কম্পিউটার

C++ এ একটি গাছে পূর্বপুরুষ-বংশের সম্পর্কের জন্য ক্যোয়ারী


এই টিউটোরিয়ালে, আমরা একটি গাছে পূর্বপুরুষ-বংশীয় সম্পর্কের জন্য অনুসন্ধানের জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব৷

এর জন্য আমাদের একটি শিকড়যুক্ত গাছ এবং Q প্রশ্ন প্রদান করা হবে। আমাদের কাজ হল অনুসন্ধানে প্রদত্ত দুটি মূল অন্যটির পূর্বপুরুষ বা না তা খুঁজে বের করা৷

উদাহরণ

#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

  1. গাছের ব্যাস C++ এ

  2. C++ এ সংযোগ বিচ্ছিন্ন গ্রাফের জন্য BFS

  3. অ্যারের উপাদানগুলির গুণনের জন্য C++ প্রোগ্রাম

  4. C++ এ অক্টাল থেকে দশমিক রূপান্তরের জন্য প্রোগ্রাম