BipartiteMatching
クラス · 二部グラフの最大マッチング（push-relabel 方式、$O(E\sqrt V)$）
struct BipartiteMatching;
概要
二部グラフの最大マッチング（push-relabel 方式、$O(E\sqrt V)$）
未マッチの右頂点が「レベル最小の左隣接頂点」を奪い、押し出された右頂点が 再びキューに戻る。左頂点のレベル（自由左頂点までの交互道長の下界）は 奪われるたびに $+2$ され（relabel）、$V$ 回のポップごとに BFS で全体を 張り直す（global relabel）。レベルが $V$ 以上に達した頂点は増強不能。 Goldberg–Kennedy の解析により $O(E\sqrt V)$。実測でも増強路ベースの Hopcroft-Karp より速い。
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
左n頂点・右m頂点の空の二部グラフを構築する | $O(n+m)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
add_edge |
左頂点uと右頂点vを結ぶ辺を追加する | 償却 $O(1)$ |
matching |
最大マッチングのサイズ | 頂点数を $V$、辺数を $E$ として初回 $O(E\sqrt V)$ |
get_pairs |
現在のマッチング辺を返す | $O(V)$ |
minimum_vertex_cover |
最小頂点被覆（König の定理） | $O(E\sqrt V)$ |
maximum_independent_set |
最大独立集合（最小頂点被覆の補集合） | $O(E\sqrt V)$ |
メンバの詳細
matching
int matching();
最大マッチングのサイズ
- 計算量: 頂点数を $V$、辺数を $E$ として初回 $O(E\sqrt V)$
- 備考: 冪等。既にマッチ済みの分も含めた総数を返すので、何度呼んでも同じ値になる。
minimum_vertex_cover
std::pair<std::vector<int>, std::vector<int>> minimum_vertex_cover();
最小頂点被覆（König の定理）
- 戻り値: (左側頂点集合, 右側頂点集合)
- 計算量: $O(E\sqrt V)$
maximum_independent_set
std::pair<std::vector<int>, std::vector<int>> maximum_independent_set();
最大独立集合（最小頂点被覆の補集合）
- 戻り値: (左側頂点集合, 右側頂点集合)
- 計算量: $O(E\sqrt V)$