Trong bài toán này, chúng ta được cung cấp một cây N đỉnh và mỗi câu truy vấn Q gồm hai giá trị i và j. Nhiệm vụ của chúng tôi là tạo một chương trình để giải quyết một Truy vấn cho mối quan hệ tổ tiên-con cháu trong một cây.
Để giải quyết từng truy vấn, chúng ta cần kiểm tra xem nút i có phải là tổ tiên của nút j trong cây hay không.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
Q = 2, query[][] = {{3, 5}, {1, 6}} Đầu ra
No Yes
Giải thích
i = 3, j = 5: The node 3 is not the ancestor of node 5. Return NO. i = 1, j = 6: The node 1 is the ancestor of node 6. Return YES.
Phương pháp tiếp cận giải pháp
Một giải pháp cho vấn đề này là sử dụng kỹ thuật duyệt cây là DFS (Tìm kiếm theo chiều sâu). Chúng tôi sẽ đi ngang từ nút thứ i và thực hiện xuống tất cả các nút con của nó và sau đó kiểm tra xem nút thứ j có phải là con của nó hay không. Một cách hiệu quả để giải quyết vấn đề là tìm ra thời gian trong và thời gian chờ của mỗi nút. Và kiểm tra xem họ có chia sẻ quan hệ tổ tiên - con cháu hay không.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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 i = 0; i < g[u].size(); i++) {
int v = g[u][i];
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];
int 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;
} Đầu ra
For query 1 : is Ancestor For query 2 : is not Ancestor