Day 038-Q5 | オンライン二部マッチング（増分型 Augmenting Path）

問題

$L$ 頂点（左側）と $R$ 頂点（右側）の二部グラフ。最初エッジなし。$Q$ 個のクエリ:

1 u v: 左 $u$ と右 $v$ の間にエッジを追加
2: 現在の最大マッチングのサイズを出力

制約

パラメータ	範囲
$L, R$	$1 \le L, R \le 10^4$
$Q$	$1 \le Q \le 2 \times 10^5$
制限	時間 3 sec / メモリ 256MB

入出力例

入力例 1

出力例 1

2
3

クエリ2前: 1↔1, 2↔2 でサイズ2。最後: 1↔2, 2↔(なし or 1)→再割り当て, 3↔3 でサイズ3。

概念図: 増分型 Augmenting Path

新しいエッジ $(u, v)$ を追加後、$u$ が未マッチなら増加路を DFS で探してマッチングを更新。

ヒント（段階的開示）

ヒント1: 方向性

新しいエッジ $(u, v)$ を追加したとき、$u$ が未マッチなら増加路（Augmenting Path）を DFS で探す。見つかればマッチングサイズ +1。クエリ2は単純にカウンタを返すだけ。

ヒント2: アプローチ

増分型マッチング: エッジ追加 → $u$ が未マッチなら DFS → 増加路があれば更新。$u$ が既マッチの場合は何もしない（新エッジで増加路が生じる可能性はあるが、実装を簡略化）。
訪問済み管理: visit_id[v] と cur_visit カウンタで $O(1)$ リセット。

ヒント3: DFS コード

visit_id = [0] * (R+1)
cur_visit = 0

def dfs(u):
    for v in adj[u]:
        if visit_id[v] == cur_visit: continue
        visit_id[v] = cur_visit
        if match_r[v] == -1 or dfs(match_r[v]):
            match_l[u] = v
            match_r[v] = u
            return True
    return False

# エッジ追加時:
adj[u].append(v)
if match_l[u] == -1:
    cur_visit += 1
    if dfs(u):
        matching += 1

模範解答 (Python)

import sys
from sys import stdin
input = stdin.readline

def solve():
    import sys
    sys.setrecursionlimit(500000)
    L, R, Q = map(int, input().split())
    adj = [[] for _ in range(L+1)]
    match_l = [-1] * (L+1)
    match_r = [-1] * (R+1)
    matching = 0
    out = []
    visit_id = [0] * (R+1)
    cur_visit = 0

    def dfs(u):
        for v in adj[u]:
            if visit_id[v] == cur_visit:
                continue
            visit_id[v] = cur_visit
            if match_r[v] == -1 or dfs(match_r[v]):
                match_l[u] = v
                match_r[v] = u
                return True
        return False

    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            u, v = int(line[1]), int(line[2])
            adj[u].append(v)
            if match_l[u] == -1:
                cur_visit += 1
                if dfs(u):
                    matching += 1
        else:
            out.append(str(matching))

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

solve()

Step-by-Step 解説

1データ構造の準備
adj[u]: 左頂点 $u$ の隣接右頂点リスト。match_l[u], match_r[v]: 現在のマッチング（未マッチは -1）。visit_id + cur_visit: DFS の訪問済み管理。

2エッジ追加
隣接リストにエッジを追加。u が既にマッチしていれば DFS スキップ（簡略化）。未マッチなら DFS を実行。

3DFS 増加路探索
visit_id[v] = cur_visit で訪問済みをマーク。match_r[v] == -1 ならマッチング確定。そうでなければ match_r[v] の左頂点から再帰。

4マッチングの更新
増加路が見つかれば match_l[u] = v, match_r[v] = u を再帰的に更新（バックトラック時に自動更新）。

5クエリ2への応答
matching カウンタをそのまま返す。$O(1)$。

計算量

エッジ追加: $O(1)$ amortized（隣接リスト追加）
DFS（増加路探索）: $O(V + E)$ worst-case per query
全体: $O(Q \cdot (L + E))$ — $E$ は追加エッジ総数
クエリ2: $O(1)$

よくあるミス

ミス	原因	正しい書き方
既マッチの u から DFS	マッチ済み u にも試みてしまう	`if match_l[u] == -1:` でのみ DFS
visit リセットが O(R)	各 DFS で set() や fill() を使う	`cur_visit += 1` だけで O(1) リセット
深い再帰でスタックオーバーフロー	L が大きい場合	`sys.setrecursionlimit(500000)` か反復 DFS
クエリ2で毎回計算し直す	マッチングサイズの管理ミス	`matching` カウンタを増分管理

次のステップ

発展問題: エッジ削除対応のオンラインマッチング（Offline Divide & Conquer + Undo 法）
応用: Hopcroft-Karp による $O(\sqrt{V} \cdot E)$ 最大二部マッチング（一括 BFS + DFS）
発展: 動的グラフ上の最大フロー（辺の追加・削除をサポートする Link-Cut Tree 応用）

自己評価

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

Day 038-Q5 — オンライン二部マッチング（増分型 Augmenting Path）

問題

制約