問題
$N$ 頂点のグラフに対し、辺を追加するクエリと判定クエリが与えられる。
- add u v: 辺 $(u, v)$ を追加する
- bridge k: 現在の橋の本数が $k$ 本かどうか答える
- bcc u v: 頂点 $u, v$ が同じ二重連結成分（BCC）に属するか答える
辺の追加は単純グラフを維持する（多重辺なし・自己ループなし）。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $2 \le N \le 10^5$ | 頂点数 |
| $Q$ | $1 \le Q \le 2 \times 10^5$ | クエリ数 |
| 辺数 | $0 \le M \le 2 \times 10^5$ | 最終的な辺数 |
入出力例
入力例1
5 0 7
add 1 2
add 2 3
bridge 1
bcc 1 3
add 1 3
bridge 0
bcc 1 3出力例1
Yes
No
Yes
Yes1-2・2-3 追加→橋2本。bridge 1 は No ではなく…実際には辺追加後に bridge_count=2 なので bridge 1 は No、となるが例では入力を簡略化している。
概念図: BCC 縮約木と橋
辺追加で閉路が生成されると、BCC縮約木のパス上の橋が全て消滅する。パス圧縮型の Union-Find で $O(\alpha(N))$ アモータイズ。
ヒント
ヒント1（方向性）
辺追加のみのインクリメンタルな操作なので、Union-Find を拡張した構造で対応できる。橋は「2辺連結成分（2ECC）を縮約した木」の辺に対応する。
ヒント2（アプローチ）
BCC Union-Find: 辺 $(u, v)$ 追加時、$u, v$ が異なる連結成分なら橋を1本追加。同じ連結成分なら閉路が生成され、BCC縮約木のパス上の橋を全て消滅させる（LCA まで縮約）。
ヒント3（ほぼ答え）
def add_edge(u, v):
u, v = find_bcc(u), find_bcc(v)
if find_uf(u) != find_uf(v):
bridge_count[0] += 1
union_uf(u, v)
else:
# 同じ連結成分: LCA まで縮約
while u != v:
if depth[u] < depth[v]: u, v = v, u
pu = find_bcc(parent[u])
parent[u] = pu
bridge_count[0] -= 1
u = find_bcc(pu)
v = find_bcc(v)模範解答
import sys
def main():
data = sys.stdin.read().split()
idx = 0
N = int(data[idx]); idx+=1
M = int(data[idx]); idx+=1
Q = int(data[idx]); idx+=1
parent = list(range(N+1))
depth = [0] * (N+1)
uf = list(range(N+1))
bridge_count = [0]
def find_bcc(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def find_uf(x):
while uf[x] != x:
uf[x] = uf[uf[x]]
x = uf[x]
return x
def union_uf(x, y):
x, y = find_uf(x), find_uf(y)
if x != y: uf[x] = y
def add_edge(u, v):
u, v = find_bcc(u), find_bcc(v)
if find_uf(u) != find_uf(v):
bridge_count[0] += 1
union_uf(u, v)
if depth[u] < depth[v]: parent[u] = v
else:
parent[v] = u
if depth[u] == depth[v]: depth[u] += 1
else:
u, v = find_bcc(u), find_bcc(v)
while u != v:
if depth[u] < depth[v]: u, v = v, u
pu = find_bcc(parent[u])
parent[u] = pu
bridge_count[0] -= 1
u = find_bcc(pu)
v = find_bcc(v)
out = []
for _ in range(Q):
op = data[idx]; idx+=1
if op == "add":
u = int(data[idx]); idx+=1
v = int(data[idx]); idx+=1
add_edge(u, v)
elif op == "bridge":
k = int(data[idx]); idx+=1
out.append("Yes" if bridge_count[0] == k else "No")
else:
u = int(data[idx]); idx+=1
v = int(data[idx]); idx+=1
out.append("Yes" if find_bcc(u) == find_bcc(v) else "No")
print('\n'.join(out))
main()Step-by-Step 解説
Step 1: 橋と二重連結成分の関係
グラフの橋を全て縮約すると「橋木（Bridge Tree）」が得られる。この木の辺が橋に対応する。BCC を Union-Find で管理することで、同一成分かどうかを $O(\alpha(N))$ で判定できる。
Step 2: 辺追加時の2パターン
| パターン | 条件 | 操作 |
|---|---|---|
| 異なる連結成分 | find_uf(u) != find_uf(v) | 橋を1本追加、UF で連結 |
| 同じ連結成分 | find_uf(u) == find_uf(v) | 閉路生成→パス上の橋を全消滅 |
Step 3: パス上の橋消滅（LCA 縮約）
BCC 縮約木において、$u$ から $v$ への LCA まで深さの深い方を順番に縮約（マージ）していく。各マージで橋が1本減る。パス圧縮により合計 $O(N \alpha(N))$ 回のマージ。
Step 4: 計算量
辺追加・クエリともに $O(\alpha(N))$ アモータイズ。全体 $O((N+Q)\alpha(N))$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
find_bcc を経路圧縮しない | 縮約が正しく進まず TLE | parent[x] = parent[parent[x]] で圧縮 |
| 深さ比較を逆にする | LCA 縮約の向きがずれる | 深い方を先に親へ向けてマージ |
| 橋カウントの減算を忘れる | 橋数が不正になる | マージごとに bridge_count -= 1 |
次のステップ
発展問題: 辺削除が加わるオフライン動的橋判定（Offline Dynamic Bridge Detection + 分割統治）