Day 108-Q2 | Block-Cut Tree（二重連結成分分解の木構造化）

問題

$N$頂点$M$辺の連結な単純無向グラフが与えられる。$Q$個のクエリ$(u,v)$（$u\neq v$）それぞれについて、$u$と$v$が同じ二重連結成分（biconnected component / block）に属するか判定せよ。

ここで「$u$と$v$が同じ二重連結成分に属する」とは、$u$と$v$を結ぶ頂点素な単純パスが2本以上存在する（あるいは辺$(u,v)$単独がブリッジであっても、その2頂点だけからなる自明なブロックとみなす）ことを意味する。

Block-Cut Tree（元の頂点ノードと、各ブロックを表す新規ノードを交互につないだ木）を構築し、その木上でのLCA（最小共通祖先）による距離を使って各クエリに$O(\log N)$で答えよ。

入力形式

N M
u_1 v_1
...
u_M v_M
Q
u_1 v_1
...
u_Q v_Q

制約

$2 \le N \le 10^5$

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

連結・自己ループ/多重辺なし

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

各クエリで $u_i \neq v_i$

入出力例

入力例1

出力例1

Yes
No
Yes
Yes
Yes
No

頂点1-2-3が三角形、頂点3-4-5が三角形で頂点3が関節点。1と2は同じ三角形なのでYes。1と4は別の三角形なのでNo。3は両方の三角形に属するので3-4, 1-3もYes。4-5もYes。2と4は別の三角形なのでNo。

入力例2

出力例2

Yes
No
Yes
No

一直線のパスグラフでは全ての辺がブリッジ。ブリッジ1本だけでも自明なブロックとみなすので、隣接する頂点同士（1-2, 2-3）はYes、間に関節点を挟む（1-3, 1-5）はNo。

概念図: 頂点層とブロック層が交互に並ぶ木

ヒント（段階的開示）

ヒント1: 方向性

「$u,v$が同じ二重連結成分か」を毎回グラフ探索で判定すると$O(Q\cdot(N+M))$になり間に合わない。二重連結成分分解を一度だけ前計算し、以降のクエリに高速に答えられる構造を作る必要がある。単純に「各頂点が属するブロックID集合」を持たせて共通ブロックの有無を調べる方法は、関節点の次数が大きいと集合の突き合わせに時間がかかってしまう。

ヒント2: アプローチ

二重連結成分分解（DFS+low-link、辺スタックを使うTarjan型アルゴリズム）で全ブロックを求めたあと、元の頂点$N$個 + ブロック$B$個、合計$N+B$個のノードからなる木を作る。各ブロックノードを、そのブロックに属する全ての元頂点と辺で結ぶ。この木は頂点層とブロック層が交互に現れる二部グラフ的な木になっており、「$u$と$v$が同じブロックに属する」ことは「木上で$u$から$v$への最短距離がちょうど$2$（間に共通のブロックノードが1つだけ挟まる）」という条件に一致する。距離は事前計算したLCA（ダブリングによる二分累乗）を使えば$O(\log N)$で求まる。

ヒント3: 誘導（コード骨格）

# 1. 辺スタックを使ったDFSで二重連結成分（ブロック）を求める
#    low[u] >= disc[p] となった時点で、辺スタックから辺を取り出して1ブロック確定
# 2. N+B個のノードで木を構築（頂点v -- ブロックノード）
# 3. BFSでdepthとparent[0]を求め、ダブリングで parent[k] を構築
# 4. クエリ(u,v): w=lca(u,v); dist = depth[u]+depth[v]-2*depth[w]; dist==2 なら Yes

模範解答 (Python)

import sys
from collections import deque

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    adj = [[] for _ in range(N + 1)]
    for i in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].append((v, i))
        adj[v].append((u, i))

    disc = [0] * (N + 1)
    low = [0] * (N + 1)
    visited = [False] * (N + 1)
    timer = 1
    edge_stack = []
    blocks = []
    it = [0] * (N + 1)

    for s in range(1, N + 1):
        if visited[s]:
            continue
        stack = [(s, -1)]
        visited[s] = True
        disc[s] = low[s] = timer; timer += 1
        while stack:
            u, pe = stack[-1]
            if it[u] < len(adj[u]):
                v, eid = adj[u][it[u]]
                it[u] += 1
                if eid == pe:
                    continue
                if not visited[v]:
                    visited[v] = True
                    disc[v] = low[v] = timer; timer += 1
                    edge_stack.append((u, v, eid))
                    stack.append((v, eid))
                else:
                    if disc[v] < disc[u]:
                        edge_stack.append((u, v, eid))
                        low[u] = min(low[u], disc[v])
            else:
                stack.pop()
                if stack:
                    p, _ = stack[-1]
                    low[p] = min(low[p], low[u])
                    if low[u] >= disc[p]:
                        comp_vertices = set()
                        while True:
                            eu, ev, eeid = edge_stack.pop()
                            comp_vertices.add(eu); comp_vertices.add(ev)
                            if eeid == pe:
                                break
                        blocks.append(comp_vertices)

    in_any_block = set()
    for b in blocks:
        in_any_block |= b
    for v in range(1, N + 1):
        if v not in in_any_block:
            blocks.append({v})

    B = len(blocks)
    bt_adj = [[] for _ in range(N + B + 1)]
    for bi, comp in enumerate(blocks):
        bnode = N + 1 + bi
        for v in comp:
            bt_adj[bnode].append(v)
            bt_adj[v].append(bnode)

    total = N + B
    LOG = max(1, total.bit_length() + 1)
    depth = [0] * (total + 1)
    parent = [[0] * (total + 1) for _ in range(LOG)]
    visited2 = [False] * (total + 1)
    dq = deque([1])
    visited2[1] = True
    order = [1]
    while dq:
        u = dq.popleft()
        for w in bt_adj[u]:
            if not visited2[w]:
                visited2[w] = True
                depth[w] = depth[u] + 1
                parent[0][w] = u
                dq.append(w)
                order.append(w)
    for k in range(1, LOG):
        pk = parent[k]; pk1 = parent[k - 1]
        for w in order:
            pk[w] = pk1[pk1[w]]

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

    Q = int(data[idx]); idx += 1
    out = []
    for _ in range(Q):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = lca(u, v)
        dist = depth[u] + depth[v] - 2 * depth[w]
        out.append("Yes" if dist == 2 else "No")
    print("\n".join(out))


solve()

計算量: 二重連結成分分解$O(N+M)$、Block-Cut Tree構築$O(N+M)$、LCA前計算$O((N+B)\log(N+B))$、クエリ1件$O(\log N)$。三角形2つが関節点で繋がるグラフとブリッジのみのパスグラフの2種類で手計算した期待値と完全一致することを確認済み。

Step-by-Step 解説

1辺スタックを使った反復DFSで二重連結成分を求める
再帰DFSは$N$が大きいと再帰上限に達するため、明示的なスタックで反復DFSを行う。discとlowを管理し、通った辺は逐次edge_stackに積む。

2low[u] >= disc[p]でブロックを確定する
子$u$の探索が終わったとき、この条件が成立すれば$p$は関節点である。edge_stackから辺$(p,u)$に到達するまで辺を取り出し、それら全ての端点集合が1つの二重連結成分となる。

3ブロックノードを追加した木を構築する
各ブロックに新規ノード番号（$N+1$以降）を割り当て、そのブロックに属する全頂点と辺で結ぶ。任意の2頂点間の最短距離は必ず偶数になる。

4ダブリングLCAで距離を$O(\log N)$で求める
木を根（頂点1）からBFSしてdepthとparent[0]を求めたあと、二分累乗テーブルを構築する。depth[u]+depth[v]-2*depth[lca]で距離を計算し、==2なら同じブロック。

よくあるミス

ミス	原因	正しい書き方
反復DFSで親辺のスキップを「頂点」で判定してしまう	多重辺がある場合、同じ頂点への複数の辺を誤って全てスキップしてしまう	親「頂点」ではなく親「辺ID」（`pe`）と比較してスキップする
後退辺の判定条件を`disc[v] != disc[u]`のように緩くしてしまう	無向グラフのDFSでは非木辺は必ず祖先への後退辺になるが、両方向から二重にカウントしてしまう	`disc[v] < disc[u]`（$v$が祖先である場合のみ）に限定する
孤立していない頂点なのにどのブロックにも属さないケースを見落とす	全頂点がいずれかのブロックに属するとは限らない特殊ケースの処理漏れ	念のため`in_any_block`に含まれない頂点を単独ブロックとして追加しておく
`dist==2`ではなく`dist<=2`で判定してしまう	$u==v$のケース（dist=0）も"同じブロック"に含めようとして条件を緩めてしまう	本問は$u\neq v$が保証されるため`dist==2`のみが「同じブロック」を意味する

次のステップ

発展: クエリを「$u$から$v$へ移動する際に必ず通過する関節点の個数」を求める形に変更する（(dist-2)//2で計算できる）
発展: 辺の追加・削除がある動的なグラフに対して二重連結成分分解を維持する（Link-Cut Treeベースのオフライン分割統治と組み合わせる）
次回予告: Cuckoo Hashing（カッコウハッシュ・2ハッシュ関数+玉突き挿入による期待O(1)探索）

自己評価

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

Day 108-Q2 — Block-Cut Tree（二重連結成分分解の木構造化）

問題