โปรแกรมตรวจสอบความสัมพันธ์บรรพบุรุษ-ลูกหลานในต้นไม้ด้วย C++

ในโจทย์นี้ ให้ต้นไม้ N โหนด และ Q คำถาม แต่ละคำถามมีคู่ (i, j) ต้องการตรวจสอบว่าโหนด i เป็นบรรพบุรุษของโหนด j หรือไม่

ตัวอย่าง:

Q = 2, query[][] = {{3, 5}, {1, 6}}

เอาต์พุต

No Yes

คำอธิบาย

i=3, j=5: โหนด 3 ไม่ใช่บรรพบุรุษของ 5 → NO
i=1, j=6: โหนด 1 เป็นบรรพบุรุษของ 6 → YES

วิธีแก้ปัญหา

ใช้ DFS คำนวณเวลาเข้า (entry time) และเวลาออก (exit time) ของแต่ละโหนด โหนด u เป็นบรรพบุรุษของ v ก็ต่อเมื่อ:

entry[u] <= entry[v] และ exit[u] >= exit[v]

ตัวอย่างโค้ด 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 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 << "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;
}

เอาต์พุต

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