C++プログラムのツリーでの祖先と子孫の関係のクエリ

この問題では、それぞれ2つの値iとjで構成されるN個の頂点ツリーと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