Bipartite Matching
(graph/bipartite_matching.hpp)
Description
二部グラフの最大マッチングを Hopcroft-Karp アルゴリズムで求める.これは Dinic のアルゴリズムの特殊ケースである.
Operations
-
BipartiteMatching(int U, int V)
-
void add_edge(int u, int v)
-
vector<pair<int, int>> max_matching()
- 二部グラフの最大マッチングを一つ返す
- 時間計算量: $O(E\sqrt{U+V})$
Reference
Required by
Verified with
Code
Back to top page