数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚
法律C++ 中的树中祖先 - 后代关系查询
在本教程中，我们将讨论一个在树中查询祖先 - 后代关系的程序。
为此，我们将提供一个根树和 Q 查询。我们的任务是找出查询中给出的两个根是否一个的另一个祖先。
示例
#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;
}输出
no
更新日期： 19-08-2020
131 浏览
广告内容