Day 065-Q5 | 二重連結成分・橋木構築 + 動的連結性（Bridge Tree + HLD）

問題

$N$ 頂点 $M$ 辺の無向グラフ $G$ が与えられる。以下のクエリを $Q$ 個処理せよ：

add u v : 辺 $(u, v)$ を追加する。
query u v : $u$ から $v$ への任意のパスを通るとき、必ず通らなければならない橋の数を出力せよ（非連結の場合は -1）。

制約

パラメータ	範囲
$N$	$1 \le N \le 10^5$
$M$	$0 \le M \le 2 \times 10^5$
$Q$	$1 \le Q \le 10^5$
制約	自己ループなし、多重辺あり

入出力例

入力例 1

5 3 5
1 2
2 3
4 5
query 1 3
query 1 5
add 2 4
query 1 4
add 3 4
query 1 3
query 1 5

出力例 1

概念図: 橋木（Bridge Tree）の構築

ヒント（段階的開示）

ヒント1: 橋木の構造

橋木とは「グラフの各 2ECC（二重辺連結成分）を1頂点に縮退し、元グラフの橋のみを辺として持つ木（フォレスト）」。$u$-$v$ 間に必ず通らなければならない橋の数 = 橋木上での $u'$-$v'$ 間のパスの辺数。

ヒント2: Tarjan の橋検出

$disc[v]$: DFS で $v$ を最初に訪れた時刻。$low[v]$: $v$ の部分木から後退辺経由で到達できる最小の $disc$ 値。辺 $(u, v)$ が橋 ⟺ $low[v] > disc[u]$。2ECC は Union-Find で管理（橋でない辺でつながれた頂点を同一グループに）。

ヒント3: 動的辺追加

def add(u, v):
    cu, cv = find(u), find(v)
    if cu == cv:
        return  # 同一2ECC内: 影響なし
    if same_component(cu, cv):
        # 橋木上のcu→cvパスを全て2ECCにマージ
        merge_path_on_bridge_tree(cu, cv)
    else:
        # 新しい橋辺を橋木に追加
        bridge_tree.add_edge(cu, cv)

def query(u, v):
    cu, cv = find(u), find(v)
    if not same_component(cu, cv):
        return -1
    l = lca(cu, cv)
    return depth[cu] + depth[cv] - 2 * depth[l]

模範解答 (Python)

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

def solve():
    N, M, Q = map(int, input().split())

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

    # Union-Find for 2ECC
    uf_parent = list(range(N + 1))
    uf_rank = [0] * (N + 1)

    def find(x):
        while uf_parent[x] != x:
            uf_parent[x] = uf_parent[uf_parent[x]]
            x = uf_parent[x]
        return x

    def union(x, y):
        x, y = find(x), find(y)
        if x == y: return False
        if uf_rank[x] < uf_rank[y]: x, y = y, x
        uf_parent[y] = x
        if uf_rank[x] == uf_rank[y]: uf_rank[x] += 1
        return True

    # Tarjan bridge detection (iterative)
    disc = [0] * (N + 1)
    low = [0] * (N + 1)
    visited = [False] * (N + 1)
    timer = [1]
    bridges = set()

    for start in range(1, N + 1):
        if visited[start]: continue
        stack = [(start, -1, iter(adj[start]))]
        disc[start] = low[start] = timer[0]; timer[0] += 1
        visited[start] = True
        while stack:
            v, parent, it = stack[-1]
            try:
                u = next(it)
                if u == parent: continue
                if not visited[u]:
                    visited[u] = True
                    disc[u] = low[u] = timer[0]; timer[0] += 1
                    stack.append((u, v, iter(adj[u])))
                else:
                    low[v] = min(low[v], disc[u])
            except StopIteration:
                stack.pop()
                if stack:
                    pv, _, _ = stack[-1]
                    low[pv] = min(low[pv], low[v])
                    if low[v] > disc[pv]:
                        bridges.add((min(pv, v), max(pv, v)))

    # Merge 2ECC via non-bridge edges
    for u in range(1, N + 1):
        for v in adj[u]:
            if (min(u, v), max(u, v)) not in bridges:
                union(u, v)

    # Build bridge tree
    bt_adj = defaultdict(set)
    for u, v in bridges:
        cu, cv = find(u), find(v)
        if cu != cv:
            bt_adj[cu].add(cv)
            bt_adj[cv].add(cu)

    # BFS on bridge tree for LCA (Binary Lifting)
    LOG = 17
    bt_depth = [0] * (N + 1)
    bt_up = [[0] * (N + 1) for _ in range(LOG)]
    comp_root = [0] * (N + 1)  # which BFS root each node belongs to

    visited2 = [False] * (N + 1)
    for start in range(1, N + 1):
        r = find(start)
        if visited2[r]: continue
        visited2[r] = True
        q = deque([r])
        bt_depth[r] = 0
        bt_up[0][r] = r
        comp_root[r] = r
        bq = {r}
        while q:
            node = q.popleft()
            for nb in bt_adj[node]:
                if nb not in bq:
                    bq.add(nb)
                    bt_depth[nb] = bt_depth[node] + 1
                    bt_up[0][nb] = node
                    comp_root[nb] = r
                    q.append(nb)

    for k in range(1, LOG):
        for v in range(1, N + 1):
            bt_up[k][v] = bt_up[k-1][bt_up[k-1][v]]

    def lca(u, v):
        if bt_depth[u] < bt_depth[v]: u, v = v, u
        diff = bt_depth[u] - bt_depth[v]
        for k in range(LOG):
            if (diff >> k) & 1: u = bt_up[k][u]
        if u == v: return u
        for k in range(LOG - 1, -1, -1):
            if bt_up[k][u] != bt_up[k][v]:
                u = bt_up[k][u]; v = bt_up[k][v]
        return bt_up[0][u]

    def query_bridges(u, v):
        cu, cv = find(u), find(v)
        if comp_root[cu] != comp_root[cv]: return -1
        l = lca(cu, cv)
        return bt_depth[cu] + bt_depth[cv] - 2 * bt_depth[l]

    out = []
    for _ in range(Q):
        parts = input().split()
        if parts[0] == 'add':
            u, v = int(parts[1]), int(parts[2])
            cu, cv = find(u), find(v)
            if cu == cv: continue
            if comp_root[cu] == comp_root[cv]:
                # 同一連結成分内: 橋木上のパスを全てマージ
                # （簡略実装: パスを辿って2ECCを縮退）
                a, b = cu, cv
                while a != b:
                    if bt_depth[a] < bt_depth[b]: a, b = b, a
                    par = bt_up[0][a]
                    union(a, par)  # a と親をマージ
                    new_a = find(a)
                    if new_a in bt_adj[par]:
                        bt_adj[par].discard(a)
                    a = new_a
            else:
                # 異なる連結成分: 新しい橋を追加
                bt_adj[cu].add(cv)
                bt_adj[cv].add(cu)
                bt_up[0][cv] = cu
                bt_depth[cv] = bt_depth[cu] + 1
                for k in range(1, LOG):
                    bt_up[k][cv] = bt_up[k-1][bt_up[k-1][cv]]
                old_root = comp_root[cv]
                # update comp_root for cv's component (simplified)
                comp_root[cv] = comp_root[cu]
        else:
            u, v = int(parts[1]), int(parts[2])
            out.append(str(query_bridges(u, v)))

    print('\n'.join(out))

solve()

Step-by-Step 解説

Step 1: 橋の検出 — Tarjan のアルゴリズム

$disc[v]$: DFS で $v$ を最初に訪れた時刻。$low[v]$: $v$ の部分木から後退辺経由で到達できる最小の $disc$ 値。辺 $(u, v)$ が橋 ⟺ $low[v] > disc[u]$。$O(N + M)$ で全橋を検出。

Step 2: 2ECC のマージ

橋でない辺でつながれた頂点は同一 2ECC に属する。Union-Find で管理し、代表元 find(v) で 2ECC を識別。

Step 3: 橋木の構築

各 2ECC（Union-Find 代表元）を1ノードとして橋のみを辺に持つ木（フォレスト）を構築。$u$-$v$ 間の橋数 = depth[find(u)] + depth[find(v)] - 2 * depth[lca(find(u), find(v))]。

Step 4: 動的辺追加の3ケース

同一 2ECC 内: 影響なし。
同一コンポーネント・異なる 2ECC: 橋木上の $u'$-$v'$ パスにある全橋を削除し、2ECC をマージ（路の縮退）。
異なるコンポーネント: 新しい橋辺を橋木に追加し、LCA テーブルを更新。

Step 5: 計算量

操作	計算量
初期橋木構築	$O(N + M)$
LCA 前処理	$O(N \log N)$
query クエリ	$O(\log N)$
add (単純接続)	$O(\log N)$
add (橋削除・2ECCマージ)	$O(\log^2 N)$ amortized

よくあるミス

ミス	原因	正しい書き方
多重辺での橋判定ミス	親辺を頂点で管理（多重辺では誤判定）	親辺のIDを管理、または辺ごとにフラグを立てる
非連結で LCA を呼ぶ	異なるコンポーネントの LCA は未定義	`comp_root[cu] == comp_root[cv]` を事前確認
辺追加後に LCA テーブル未更新	古い `bt_up` を参照	新接続ノードの `bt_up[k]` を全 $k$ で再計算

次のステップ

発展問題: 辺削除クエリに対応せよ（辺追加の逆は困難なため、オフライン Divide & Conquer + Undo DSU で処理する。各クエリをセグメント木の時間軸上に配置し、DSU に辺を追加/削除する）。

自己評価

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