이 문제에서는 N개의 정점 트리와 각각 두 개의 값 i와 j로 구성된 Q 쿼리가 제공됩니다. 우리의 임무는 트리에서 조상-후손 관계에 대한 쿼리를 해결하는 프로그램을 만드는 것입니다.
각 쿼리를 해결하려면 노드 i가 트리에서 노드 j의 조상인지 확인해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
Q = 2, query[][] = {{3, 5}, {1, 6}} 출력
No Yes
설명
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.
솔루션 접근 방식
이 문제에 대한 해결책은 DFS(깊이 우선 탐색)인 트리 탐색 기술을 사용하는 것입니다. 우리는 i번째 노드에서 트래버스하고 모든 자손을 수행한 다음 j번째 노드가 그것의 자손인지 확인합니다. 문제를 해결하는 효율적인 방법은 각 노드의 타임 인 및 타임 아웃을 찾는 것입니다. 그리고 조상-후손 관계를 공유하는지 확인하십시오.
우리 솔루션의 작동을 설명하는 프로그램
예시
#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;
} 출력
For query 1 : is Ancestor For query 2 : is not Ancestor