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

সমস্যা বিবরণ

একটি N নোডের ট্রি এবং Qটি কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরিতে দুটি মান i এবং j থাকে। নোড i কি নোড j-এর পূর্বপুরুষ (ancestor) কিনা তা যাচাই করতে হবে।

উদাহরণ:

ইনপুট: Q = 2, query[][] = {{3, 5}, {1, 6}}

আউটপুট: No Yes

ব্যাখ্যা: নোড ৩, নোড ৫-এর পূর্বপুরুষ নয়। নোড ১, নোড ৬-এর পূর্বপুরুষ।

সমাধানের পদ্ধতি

DFS সময়-ট্র্যাকিং (Time-in / Time-out) পদ্ধতি:

1. DFS ট্রভার্সাল করে প্রতিটি নোডের entryTime (প্রবেশ সময়) এবং exitTime (নির্গমন সময়) রেকর্ড করুন।
2. নোড u, নোড v-এর পূর্বপুরুষ হলে শর্ত: entryTime[u] <= entryTime[v] && exitTime[u] >= exitTime[v]।
3. প্রতিটি কোয়েরি O(1) সময়ে সমাধান করুন।

উদাহরণ কোড

#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 v : g[u]) {
        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], 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