Truy vấn quan hệ tổ tiên - con cháu trong cây trong C++

Mô tả bài toán

Cho cây N đỉnh và Q truy vấn, mỗi truy vấn gồm hai đỉnh i, j. Kiểm tra xem đỉnh i có phải là tổ tiên của đỉnh j hay không.

Ví dụ: Cây với cạnh {{0,1},{0,2},{1,3},{1,4},{4,5},{5,6},{5,7}}, truy vấn {{3,5},{1,6}} → kết quả "No Yes".

Giải pháp

Sử dụng DFS để tính thời gian vào (entTime) và thời gian ra (exitTime) của mỗi đỉnh. Đỉnh u là tổ tiên của v nếu và chỉ nếu entTime[u] ≤ entTime[v] và exitTime[u] ≥ exitTime[v].

Ví dụ minh họa (C++)

#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 V = 8, 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) << " : ";
        if (entTime[query[i][0]] <= entTime[query[i][1]] && exitTime[query[i][0]] >= exitTime[query[i][1]])
            cout << "is Ancestor\n";
        else
            cout << "is not Ancestor\n";
    }
    return 0;
}

Đầu ra

For query 1 : is not Ancestor
For query 2 : is Ancestor