Day 138-Q5 | 橋を跨ぐパスクエリ

問題

$N$頂点$M$辺の連結な単純無向グラフが与えられる。取り除くとグラフが非連結になる辺を橋と呼ぶ。$Q$個のクエリ$(u,v)$に対し、「$u$から$v$へ至る任意の単純path上に必ず現れる橋の本数」を求めよ。

橋を全て取り除いてできる連結成分（2-edge-connected components）を1つの頂点に縮約し、橋だけを辺として繋いだ木（bridge tree）を作ると、答えはその木の上での$u$の属す成分と$v$の属す成分の間の距離に一致する。

入力形式

N M
u_1 v_1
...
u_M v_M
Q
q_1_u q_1_v
...
q_Q_u q_Q_v

制約

$2 \le N \le 2\times10^5$

$N-1 \le M \le 2\times10^5$

グラフは連結・単純

$1 \le Q \le 2\times10^5$

入出力例

入力例1

出力例1

2
1
0

頂点1,2,3と4,5,6はそれぞれ三角形。3-4と6-7が橋。1→7は橋2本、1→5は橋1本、2→3は同じ三角形内で橋を跨がない。

概念図

ヒント（段階的開示）

ヒント1（方向性）

「橋を跨ぐ本数」は経路の取り方に依存しない不変量である。橋を全部取り除いた残り(2-edge-connected components)の内部には、どの2点間にも橋を使わない別の経路が必ず存在するため、$u,v$間のどの単純pathを選んでも通過する橋の集合は変わらない。この「橋を使わない部分は1つの塊とみなしてよい」という観察がグラフを木に単純化する鍵。

ヒント2（アプローチ）

①low-link法(DFS帰りがけ順で$low[v]=\min(disc[v],\dots)$)で全ての橋を非再帰DFSで検出する。②橋でない辺だけでUnion-Findを構築し、各頂点の2-edge-connected componentを求める。③橋だけを辺として成分同士を繋ぐ木を作る。④木の上で二分累乗LCAを前計算し、クエリ$(u,v)$に$depth[a]+depth[b]-2depth[lca(a,b)]$を答える。

ヒント3（誘導）

def find_bridges(N, adj):
    visited=[False]*(N+1); disc=[0]*(N+1); low=[0]*(N+1)
    is_bridge=[False]*len(edges); timer=1
    for s in range(1,N+1):
        if visited[s]: continue
        visited[s]=True; disc[s]=low[s]=timer; timer+=1
        stack=[(s,-1,iter(adj[s]))]
        while stack:
            v,pe,it = stack[-1]; moved=False
            for to,eid in it:
                if eid==pe: continue
                if not visited[to]:
                    visited[to]=True; disc[to]=low[to]=timer; timer+=1
                    stack.append((to,eid,iter(adj[to]))); moved=True; break
                else:
                    low[v]=min(low[v],disc[to])
            if not moved:
                stack.pop()
                if stack:
                    p=stack[-1][0]
                    low[p]=min(low[p],low[v])
                    if low[v]>disc[p]:
                        is_bridge[pe]=True
    return is_bridge

橋の縮約後は頂点数が最大$N$の木になるので、通常の二分累乗LCAテンプレートがそのまま使える。

模範解答 (Python)

import sys


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    edges = []
    adj = [[] for _ in range(N + 1)]
    for eid in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        edges.append((u, v))
        adj[u].append((v, eid))
        adj[v].append((u, eid))

    # --- 橋検出（非再帰 low-link 法） ---
    visited = [False] * (N + 1)
    disc = [0] * (N + 1)
    low = [0] * (N + 1)
    is_bridge = [False] * M
    timer = 1
    for s in range(1, N + 1):
        if visited[s]:
            continue
        visited[s] = True
        disc[s] = low[s] = timer; timer += 1
        stack = [(s, -1, iter(adj[s]))]
        while stack:
            v, pe, it = stack[-1]
            moved = False
            for to, eid in it:
                if eid == pe:
                    continue
                if not visited[to]:
                    visited[to] = True
                    disc[to] = low[to] = timer; timer += 1
                    stack.append((to, eid, iter(adj[to])))
                    moved = True
                    break
                else:
                    if disc[to] < low[v]:
                        low[v] = disc[to]
            if not moved:
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    if low[v] < low[p]:
                        low[p] = low[v]
                    if low[v] > disc[p]:
                        is_bridge[pe] = True

    # --- Union-Find で橋以外を縮約 ---
    parent = list(range(N + 1))

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

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb

    for eid, (u, v) in enumerate(edges):
        if not is_bridge[eid]:
            union(u, v)

    # --- 縮約木の構築 ---
    comp_adj = [[] for _ in range(N + 1)]
    for eid, (u, v) in enumerate(edges):
        if is_bridge[eid]:
            cu, cv = find(u), find(v)
            comp_adj[cu].append(cv)
            comp_adj[cv].append(cu)

    # --- 二分累乗LCAの前計算（非再帰BFS） ---
    LOG = max(1, (N).bit_length())
    depth = [0] * (N + 1)
    up = [[0] * (N + 1) for _ in range(LOG)]
    visited2 = [False] * (N + 1)

    root = find(1)
    visited2[root] = True
    order = [root]
    head = 0
    while head < len(order):
        v = order[head]; head += 1
        for to in comp_adj[v]:
            if not visited2[to]:
                visited2[to] = True
                depth[to] = depth[v] + 1
                up[0][to] = v
                order.append(to)

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

    def lca(a, b):
        if depth[a] < depth[b]:
            a, b = b, a
        diff = depth[a] - depth[b]
        for k in range(LOG):
            if (diff >> k) & 1:
                a = up[k][a]
        if a == b:
            return a
        for k in range(LOG - 1, -1, -1):
            if up[k][a] != up[k][b]:
                a = up[k][a]
                b = up[k][b]
        return up[0][a]

    Q = int(data[idx]); idx += 1
    out = []
    for _ in range(Q):
        qu = int(data[idx]); idx += 1
        qv = int(data[idx]); idx += 1
        cu, cv = find(qu), find(qv)
        if cu == cv:
            out.append("0")
        else:
            l = lca(cu, cv)
            out.append(str(depth[cu] + depth[cv] - 2 * depth[l]))

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


main()

Step-by-Step 解説

1橋検出の非再帰化
Nが最大2×10^5のためPythonの再帰DFSはスタックオーバーフローの危険がある。「頂点・親辺番号・隣接リストのイテレータ」をタプルでスタックに積み、イテレータが尽きたらpopして親のlowを更新する。

2橋の判定条件
頂点vとその子c(DFS木の辺)について、low[c]>disc[v]が成り立つとき辺(v,c)は橋である。cの部分木からvより浅い場所へ戻る後退辺が1本もないことを意味する。

3Union-Findによる縮約
橋でない辺だけでUnion-Findを構築すると、各連結成分が2-edge-connected componentになる。

4縮約木の構築とLCA
橋だけを辺として成分の代表元同士を結ぶと木ができる。木の上で二分累乗LCAを前計算すれば任意の2成分間の距離(=橋の本数)をO(log N)で求められる。

5クエリ処理
find(u),find(v)で成分を求め、同じ成分なら0、異なれば距離公式depth[a]+depth[b]-2*depth[lca(a,b)]で橋の本数を求める。

よくあるミス

ミス	原因	正しい書き方
再帰DFSで橋検出を実装しREになる	N=2×10^5で再帰深さが上限を超える	必ず非再帰(明示スタック)で実装する
親辺の除外を頂点で判定する	多重辺がある場合に誤って両方除外し橋を誤判定する	頂点ではなく辺番号(eid==pe)で親辺を除外する
縮約木の頂点と元頂点番号を混同する	縮約木の頂点集合は各成分の代表元だけである	LCAの計算では常にfind()を通した代表元を使う
up配列のLOGに余裕を持たせない	二分累乗の桁数が1つ足りず正しくジャンプできない	LOG=N.bit_length()程度で十分だが境界ケースも考慮しmax(1,...)にする
同じ成分に属するクエリの0本ケースを見落とす	常に橋を跨ぐ前提でLCA計算してしまう	find(u)==find(v)なら即座に0を返す分岐を先頭に置く

次のステップ

発展: 「u-v間の橋のうち辺番号が最小のもの」や「通過する橋の一覧」を復元するクエリに拡張せよ(縮約木上のパス復元+各木辺に対応する元の橋番号を持たせる)。
発展2: オンラインで橋の追加・削除に対応する場合、Euler Tour TreeやLink-Cut Treeベースの高度なデータ構造が必要になる。Day110-Q2・Day055を復習し本問との違いを整理せよ。

自己評価

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

Day 138-Q5 — 橋を跨ぐパスクエリ（2-edge-connected components縮約木+LCA）

問題