সমস্যা
একটি রুটেড ট্রি এবং Q কুয়েরি দেওয়া। প্রতিটি কুয়েরিতে দুটি নোড u, v দেওয়া থাকবে। যাচাই করুন u কি v-এর অ্যানসেস্টার (প্রাজ্ঞ) বা v কি u-এর অ্যানসেস্টার।
অ্যালগরিদম: DFS টাইমস্ট্যাম্প (In-time / Out-time)
- DFS ট্রাভার্সালে প্রতিটি নোডের
tin[u](প্রবেশ সময়) এবংtout[u](প্রস্থান সময়) রেকর্ড করুন। uহলv-এর অ্যানসেস্টার ⟺tin[u] <= tin[v] && tout[v] <= tout[u]।
C++ কোড
#include <bits/stdc++.h>
using namespace std;
void dfs(vector<int> g[], int u, int parent, int tin[], int tout[], int& timer) {
tin[u] = ++timer;
for (int v : g[u]) if (v != parent)
dfs(g, v, u, tin, tout, timer);
tout[u] = ++timer;
}
bool isAncestor(int u, int v, int tin[], int tout[]) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int main() {
int edges[][2] = {{0,1},{0,2},{1,3},{1,4},{2,5}};
int V = 6;
vector<int> g[V];
for (auto &e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
int tin[V], tout[V], timer = 0;
dfs(g, 0, -1, tin, tout, timer);
cout << (isAncestor(1,5,tin,tout) ? "yes" : "no"); // no
}
আউটপুট
no
কমপ্লেক্সিটি
- প্রিপ্রসেসিং: O(V+E)
- প্রতি কুয়েরি: O(1)
