Day 026-Q1 — Dominator Tree 応用 (Lengauer-Tarjan + Euler Tour)

問題

有向グラフとソース $s$。Dominator Tree を構築し、各クエリ $(u, v)$ について「$s$ から $v$ への全パスが必ず $u$ を通るか（$u$ が $v$ の祖先か）」に答えよ。

制約

入出力例

6 7
1 2
1 3
2 4
3 4
4 5
2 6
3 6
1
3
1 5
2 5
3 5

Yes
No
No

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from collections import defaultdict
input = sys.stdin.readline

def solve():
    sys.setrecursionlimit(300000)
    N, M = map(int, input().split())
    graph = defaultdict(list)
    rgraph = defaultdict(list)
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        graph[u].append(v); rgraph[v].append(u)
    s = int(input()) - 1

    n = N
    parent = [-1] * n
    semi = [-1] * n
    vertex = []
    label = list(range(n))
    ancestor = [-1] * n
    idom = [-1] * n
    bucket = defaultdict(list)

    visited = [False] * n
    stack = [(s, -1)]
    while stack:
        v, p = stack.pop()
        if visited[v]: continue
        visited[v] = True
        semi[v] = len(vertex)
        vertex.append(v)
        parent[v] = p
        for u in graph[v]:
            if not visited[u]:
                stack.append((u, v))

    def compress(v):
        if ancestor[ancestor[v]] != -1:
            compress(ancestor[v])
            if semi[label[ancestor[v]]] < semi[label[v]]:
                label[v] = label[ancestor[v]]
            ancestor[v] = ancestor[ancestor[v]]

    def eval_node(v):
        if ancestor[v] == -1: return v
        compress(v); return label[v]

    for i in range(len(vertex) - 1, 0, -1):
        w = vertex[i]
        for v in rgraph[w]:
            if semi[v] == -1: continue
            u = eval_node(v)
            if semi[u] < semi[w]:
                semi[w] = semi[u]
        bucket[vertex[semi[w]]].append(w)
        ancestor[w] = parent[w]
        pw = parent[w]
        for v in bucket[pw]:
            u = eval_node(v)
            idom[v] = u if semi[u] < semi[v] else pw
        bucket[pw].clear()

    for i in range(1, len(vertex)):
        w = vertex[i]
        if idom[w] != vertex[semi[w]]:
            idom[w] = idom[idom[w]]
    idom[s] = s

    dtree = defaultdict(list)
    for v in range(n):
        if v != s and idom[v] != -1:
            dtree[idom[v]].append(v)

    tin = [-1] * n; tout = [-1] * n
    timer = [0]
    stack = [(s, False)]
    while stack:
        v, leaving = stack.pop()
        if leaving:
            tout[v] = timer[0]; timer[0] += 1
        else:
            tin[v] = timer[0]; timer[0] += 1
            stack.append((v, True))
            for u in dtree[v]:
                stack.append((u, False))

    def is_ancestor(u, v):
        if tin[u] == -1 or tin[v] == -1: return False
        return tin[u] <= tin[v] and tout[v] <= tout[u]

    Q = int(input())
    results = []
    for _ in range(Q):
        a, b = map(int, input().split())
        results.append("Yes" if is_ancestor(a - 1, b - 1) else "No")
    print('\n'.join(results))

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• Dominator Tree 上の部分木 DP（最大独立集合など）

自己評価

自分の回答

気づき・メモ