Day 012-Q4 — 高度グラフ（Dominator Tree）

問題

有向グラフ G（頂点 0〜N-1、辺数 M）と根 r=0 が与えられる。各頂点 v の「即時支配者（immediate dominator）」を求めよ。u が v を支配するとは、r から v への全パスが u を通ること。idom[r] = -1。

制約

入出力例

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

-1
0
0
0
3
3

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(300000)

def solve():
    N, M = map(int, input().split())
    adj = defaultdict(list)
    radj = defaultdict(list)
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v)
        radj[v].append(u)

    root = 0
    order = []
    parent = [-1] * N
    semi = list(range(N))
    idom = [-1] * N
    vertex = [-1] * N
    label = list(range(N))
    ancestor = [-1] * N
    num = [-1] * N

    visited = [False] * N
    stack = [(root, -1, False)]
    while stack:
        v, p, back = stack.pop()
        if back:
            pass
        else:
            if visited[v]:
                continue
            visited[v] = True
            num[v] = len(order)
            vertex[len(order)] = v
            order.append(v)
            parent[v] = p
            for w in adj[v]:
                if not visited[w]:
                    stack.append((w, v, False))

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

    def link(v, w):
        ancestor[w] = v

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

    bucket = defaultdict(list)
    for i in range(len(order) - 1, 0, -1):
        w = vertex[i]
        for v in radj[w]:
            if num[v] == -1:
                continue
            u = eval_(v)
            if num[semi[u]] < num[semi[w]]:
                semi[w] = semi[u]
        bucket[vertex[num[semi[w]]]].append(w)
        link(parent[w], w)
        for v in bucket[parent[w]]:
            u = eval_(v)
            if num[semi[u]] < num[semi[v]]:
                idom[v] = u
            else:
                idom[v] = parent[w]
        bucket[parent[w]].clear()

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

    idom[root] = -1
    for v in range(N):
        print(idom[v])

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• Dominator Tree を使った強連結成分検出
• Virtual Tree（Auxiliary Tree）の構築

自己評価

自分の回答

気づき・メモ