Day 129-Q2 | 支配木（Dominator Tree）

問題

根 $R$ から到達可能な有向グラフが与えられる。頂点 $v$（$v \ne R$）の支配者とは、根から$v$へのすべてのパスが必ず通る頂点。$v$自身を除く支配者のうち最も近いものを即時支配者 $\mathrm{idom}(v)$ と呼ぶ。すべての頂点の即時支配者を求めよ。

入力形式

N M R
u_1 v_1
...
u_M v_M

制約

$1 \le N \le 200000$

$0 \le M \le 400000$

$1 \le R \le N$

$1 \le u_i, v_i \le N$

入出力例

入力例1

出力例1

0 1 1 1 4 1

頂点1..6の即時支配者。根は0。頂点6は「1-2-4-5-6」（3を通らない経路）が存在するためidom(6)=1（3ではない）。

概念図

ヒント（段階的開示）

ヒント1（方向性）

厳密最適はLengauer-Tarjan（半支配者を使う$O(M\log N)$）だが実装が複雑。実務でよく使われるCooper-Harvey-Kennedyの反復法（$O((N+M)\log N)$程度、実装が直感的）を扱う。

ヒント2（アプローチ）

根からのDFSで逆行きがけ順（RPO）を求める。各頂点$b$について「確定済み前任者の即時支配者どうしの共通祖先」を求めて更新する操作をRPO順に繰り返し、変化がなくなるまで全体を反復する。

ヒント3（誘導）

def intersect(u, v):
    while u != v:
        while post_num[u] < post_num[v]:
            u = idom[u]
        while post_num[v] < post_num[u]:
            v = idom[v]
    return u

postorder番号が小さい方（根から遠い方）をidomを辿って追いつかせる。一致した点が共通の支配者。

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    r = int(data[idx]); idx += 1

    adj = [[] for _ in range(n + 1)]
    radj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].append(v)
        radj[v].append(u)

    visited = [False] * (n + 1)
    postorder = []
    stack = [(r, iter(adj[r]))]
    visited[r] = True
    while stack:
        node, it = stack[-1]
        advanced = False
        for nxt in it:
            if not visited[nxt]:
                visited[nxt] = True
                stack.append((nxt, iter(adj[nxt])))
                advanced = True
                break
        if not advanced:
            postorder.append(node)
            stack.pop()

    post_num = [-1] * (n + 1)
    for i, node in enumerate(postorder):
        post_num[node] = i

    rpo = postorder[::-1]

    idom = [-1] * (n + 1)
    idom[r] = r

    def intersect(u, v):
        while u != v:
            while post_num[u] < post_num[v]:
                u = idom[u]
            while post_num[v] < post_num[u]:
                v = idom[v]
        return u

    changed = True
    while changed:
        changed = False
        for b in rpo:
            if b == r or not visited[b]:
                continue
            new_idom = -1
            for p in radj[b]:
                if idom[p] != -1:
                    new_idom = p if new_idom == -1 else intersect(new_idom, p)
            if new_idom != -1 and idom[b] != new_idom:
                idom[b] = new_idom
                changed = True

    out = []
    for v in range(1, n + 1):
        if not visited[v]:
            out.append('-1')
        elif v == r:
            out.append('0')
        else:
            out.append(str(idom[v]))
    print(' '.join(out))


solve()

Step-by-Step 解説

1逆行きがけ順(RPO)の準備
根からのDFSで帰りがけ順を求め、逆順にしたものがRPO。前任者候補はおおむね自分より前に処理される。

2初期化
根のidomは自分自身（番兵）。他は未確定(-1)。

3反復更新
RPO順に確定済み前任者どうしをintersectで合流させる。未確定の前任者は無視して後の反復で拾う。

4intersectの仕組み
postorder番号が小さい方（後で確定した方）を自分のidomを辿って追いつかせ、一致した点を共通支配者とする。

5収束と計算量
ループ構造があると1回では確定しないため変化がなくなるまで反復。実用上は数回で収束、全体$O((N+M)\log N)$程度。

よくあるミス

ミス	原因	正しい書き方
RPOではなくBFS順で反復する	収束が遅い・誤った結果	必ずDFS帰りがけ順を逆にしたRPOを使う
intersectを到達順で比較する	大小関係の意味の取り違え	postorder番号は根に近いほど大きい、という向きを正確に使う
1回のパスで収束したと決めつける	ループ・逆辺がある場合の反例	`changed`フラグで変化がなくなるまで反復する
未到達頂点を0として扱う	根と未到達の混同	未到達は-1、根だけ0として区別する

次のステップ

発展: 支配木が構築できれば「頂点削除で到達不能になる集合」を部分木クエリに帰着できる。真に最悪計算量が必要ならLengauer-Tarjanに挑戦する
次回予告: Booth's Algorithm（巡回文字列の辞書順最小回転）

自己評価

完全理解おおむね理解要復習

Day 129-Q2 — 支配木（Dominator Tree）

問題