Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm truy vấn cho mối quan hệ tổ tiên - con cháu trong một cây.
Đối với điều này, chúng tôi sẽ được cung cấp một cây gốc và các truy vấn Q. Nhiệm vụ của chúng ta là tìm hai gốc được đưa ra trong truy vấn có phải là gốc của câu kia hay không.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
//using DFS to find the relation between
//given nodes
void performingDFS(vector<int> g[], int u, int parent,
int timeIn[], int timeOut[], int& count) {
timeIn[u] = count++;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v != parent)
performingDFS(g, v, u, timeIn, timeOut, count);
}
//assigning out-time to a node
timeOut[u] = count++;
}
void processingEdges(int edges[][2], int V, int timeIn[], int timeOut[]) {
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 count = 0;
performingDFS(g, 0, -1, timeIn, timeOut, count);
}
//checking if one is ancestor of another
string whetherAncestor(int u, int v, int timeIn[], int timeOut[]) {
bool b = (timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u]);
return (b ? "yes" : "no");
}
int main() {
int edges[][2] = {
{ 0, 1 },
{ 0, 2 },
{ 1, 3 },
{ 1, 4 },
{ 2, 5 },
};
int E = sizeof(edges) / sizeof(edges[0]);
int V = E + 1;
int timeIn[V], timeOut[V];
processingEdges(edges, V, timeIn, timeOut);
int u = 1;
int v = 5;
cout << whetherAncestor(u, v, timeIn, timeOut) << endl;
return 0;
} Đầu ra
no