Truy vấn quan hệ tổ tiên - hậu duệ trong cây bằng C++

Cho cây gốc (rooted tree) và Q truy vấn. Xác định xem nút u có phải tổ tiên của v hay không.

Thuật toán: DFS + Thời gian vào/ra (Euler Tour)

• DFS từ gốc, gán tin[u] (thời gian vào) và tout[u] (thời gian ra).
• u là tổ tiên của v ⟺ tin[u] <= tin[v] && tout[v] <= tout[u].
• Mỗi truy vấn trả lời O(1).

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<int> g[], int u, int p, vector<int>& tin, vector<int>& tout, int& timer) {
    tin[u] = timer++;
    for (int v : g[u]) if (v != p) dfs(g, v, u, tin, tout, timer);
    tout[u] = timer++;
}

bool isAncestor(int u, int v, const vector<int>& tin, const vector<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]);
    }
    
    vector<int> tin(V), tout(V);
    int timer = 0;
    dfs(g, 0, -1, tin, tout, timer);
    
    cout << (isAncestor(1, 5, tin, tout) ? "yes" : "no") << endl; // no
    cout << (isAncestor(1, 3, tin, tout) ? "yes" : "no") << endl; // yes
    return 0;
}

Kết quả

no
yes

Độ phức tạp: O(V+E) tiền xử lý, O(1) mỗi truy vấn.