Day 096-Q2 | Bitset高速化二部マッチング

問題

左側 $N$ 頂点、右側 $M$ 頂点からなる二部グラフが $K$ 本の辺で与えられる。最大マッチングのサイズを求めよ。

グラフは密である可能性があり（$K$ が大きい）、通常の Kuhn 法（各頂点で隣接リストを線形走査する DFS 増加路探索、計算量 $O(NK)$）では定数倍が大きくなりすぎる場面がある。Python の多倍長整数をビットセットとして使い、隣接リストの走査を「まだ試していない隣接頂点の集合」とのビット演算に置き換えることで、実用的に高速化せよ。

入力形式

N M K
a_1 b_1
:
a_K b_K

$a_i$（左側）、$b_i$（右側）は1-indexed。同じ辺の重複はない。

制約

$1 \le N, M \le 3000$

$0 \le K \le \min(NM, 2\times10^5)$

辺の重複なし

右頂点数分のビット幅の整数で表現可能

入出力例

入力例1

出力例1

左1-右1、左2-右2、左3-右3 という完全マッチングが存在する。

概念図

ヒント（段階的開示）

ヒント1: 方向性

通常の Kuhn 法では、頂点 $u$ の DFS で「$u$ の隣接頂点のうち、まだこの DFS 中に訪れていないもの」を1つずつ順に試す。この「隣接集合から訪問済み集合を引く」操作をビット演算1回で済ませられないか考えよ。

ヒント2: アプローチ

各左頂点 $u$ の隣接情報を、右頂点数ビットの整数（Python の任意精度整数）として持つ: `adj[u]` の $j$ ビット目が1なら $u$ と右頂点 $j$ に辺がある。DFS中の「訪問済み右頂点集合」も同様にビット集合として持ち、`adj[u] & ~used` で「未訪問かつ隣接」な頂点集合が一度に求まる。最下位ビットを取り出すには `x & (-x)` を使う。

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

def try_kuhn(u, used):
    cand = adj[u] & ~used[0]
    while cand:
        low = cand & (-cand)
        v = low.bit_length() - 1
        cand ^= low
        used[0] |= low
        if match_r[v] == -1 or try_kuhn(match_r[v], used):
            match_r[v] = u
            return True
    return False

各左頂点 $u$ に対して `used = [0]` を新しく用意して `try_kuhn(u, used)` を呼び、成功したらマッチング数を1増やす。

模範解答 (Python)

import sys


def solve():
    sys.setrecursionlimit(10000)
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    k = int(data[idx]); idx += 1

    adj = [0] * n
    for _ in range(k):
        a = int(data[idx]) - 1; idx += 1
        b = int(data[idx]) - 1; idx += 1
        adj[a] |= (1 << b)

    match_r = [-1] * m

    def try_kuhn(u, used):
        cand = adj[u] & ~used[0]
        while cand:
            low = cand & (-cand)
            v = low.bit_length() - 1
            cand ^= low
            used[0] |= low
            if match_r[v] == -1 or try_kuhn(match_r[v], used):
                match_r[v] = u
                return True
        return False

    result = 0
    for u in range(n):
        used = [0]
        if try_kuhn(u, used):
            result += 1

    print(result)


solve()

計算量: 理論上は最悪 $O(NK)$ だが、内側ループが多倍長整数のビット演算（C実装）に置き換わるため実測で大幅に高速化。ビット演算1回あたり $O(M/64)$。

Step-by-Step 解説

1隣接集合をビットマスク化
各左頂点 $u$ について `adj[u] |= (1 << b)` でビットを立てる。

2`used` を DFS 中の可変状態として共有
Python の int はイミュータブルなので `used = [0]` とリストで包み `used[0] |=` により参照を保ったまま更新する。

3候補集合からの最下位ビット取り出し
`low = cand & (-cand)` は2の補数の性質を利用した最下位ビット抽出イディオム。`bit_length()-1` で頂点番号を得る。

4通常の Kuhn 法と同じ増加路探索
`match_r[v]` が空き、または再帰的に付け替え可能なら $u$ を $v$ にマッチさせる。

よくあるミス

ミス	原因	正しい書き方
`used` を通常の int で持ち更新が反映されない	int の再代入は別オブジェクトになる	`used = [0]` とリストで包み `used[0] \|=` で更新
最下位ビット抽出を `cand & 1` などで代用	ビット演算イディオムを知らない	`low = cand & (-cand)` を使う
再帰が深くなり `RecursionError`	左頂点数が多いときの DFS 連鎖	`sys.setrecursionlimit` を余裕を持って設定する
ビット位置を1-indexedのまま使う	インデックスのオフセットミス	読み込み時に必ず `-1` して0-indexedに揃える

次のステップ

発展: Hopcroft-Karp 法（層別BFS + ブロッキングフロー）と組み合わせ $O(E\sqrt V)$ にビットセット高速化を併用する
発展: 右頂点数が巨大な場合、固定長ワード配列に分割してキャッシュ効率をさらに上げる
次回予告: セグメント木で高速化した First-Fit-Decreasing（ビンパッキング近似アルゴリズム）

自己評価

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

Day 096-Q2 — Bitset高速化二部マッチング（Kuhn法の整数ビット演算高速化）

問題