C++で木構造の祖先・子孫関係を判定するクエリ処理の実装方法

問題概要

頂点数 N の木と、Q 個のクエリが与えられます。各クエリは 2 つの整数 i と j から構成され、木の中でノード i がノード j の祖先にあたるかどうかを判定するのが課題です。

具体例で動きを確認してみましょう。

入力

Q = 2, query[][] = {{3, 5}, {1, 6}}

出力

No Yes

解説

i = 3, j = 5 : ノード 3 はノード 5 の祖先ではない → No
i = 1, j = 6 : ノード 1 はノード 6 の祖先である → Yes

解法のアプローチ

最も単純な方法は、DFS(深さ優先探索)によってノード i からすべての子孫をたどり、その中にノード j が含まれているかを確認することです。ただし、この方法ではクエリごとに最大 O(N) の計算が必要になるため、クエリ数が多いケースでは非効率になります。

そこで有効なのが、DFS の探索順序を利用したタイムスタンプ法(オイラーツアー)です。各ノードについて、探索で入った時刻(entTime)と抜けた時刻(exitTime)を記録しておくと、次の重要な性質が成り立ちます。

ノード i がノード j の祖先 ⟺ entTime[i] ≤ entTime[j] かつ exitTime[j] ≤ exitTime[i]

これは「子孫の区間は必ず祖先の区間に完全に含まれる」というオイラーツアーの性質に基づいています。前処理に O(N)、各クエリの判定は O(1) で完了するため、N 頂点・Q クエリ全体を O(N + Q) で処理できます。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

// DFS で各頂点の進入時刻と退出時刻を記録する
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++;
}

// 辺リストから隣接リストを構築し、根(0)から DFS を開始する
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) << " : ";
        // i が j の祖先 ⇔ 区間 [entTime[j], exitTime[j]] が [entTime[i], exitTime[i]] に含まれる
        if (entTime[query[i][0]] <= entTime[query[i][1]] && exitTime[query[i][1]] <= exitTime[query[i][0]])
            cout << "is Ancestor\n";
        else
            cout << "is not Ancestor\n";
    }
    return 0;
}

出力

For query 1 : is not Ancestor
For query 2 : is Ancestor

クエリ 1(ノード 3 とノード 5)では 3 は 5 の祖先ではないため "is not Ancestor"、クエリ 2(ノード 1 とノード 6)では 1 は 6 の祖先であるため "is Ancestor" と正しく判定されています。

この手法を使えば、大量のクエリが発生する場面でも高速に祖先・子孫関係を判定でき、LCA(最小共通祖先)を求める問題などへの応用も可能です。