C++ Library for Competitive Programming
/*
* @title グラフ/フロー/マッチング/Hopcroft–Karp algorithm
*
* verification-helper: PROBLEM https://judge.yosupo.jp/problem/bipartitematching
*/
#include <iostream>
#include "emthrm/graph/flow/matching/hopcroft-karp_algorithm.hpp"
int main() {
int l, r, m;
std::cin >> l >> r >> m;
emthrm::HopcroftKarp hopcroft_karp(l, r);
while (m--) {
int a, b;
std::cin >> a >> b;
hopcroft_karp.add_edge(a, b);
}
std::cout << hopcroft_karp.solve() << '\n';
for (int i = 0; i < l; ++i) {
if (hopcroft_karp.match[i] != -1) {
std::cout << i << ' ' << hopcroft_karp.match[i] - l << '\n';
}
}
return 0;
}
#line 1 "test/graph/flow/matching/hopcroft-karp_algorithm.test.cpp"
/*
* @title グラフ/フロー/マッチング/Hopcroft–Karp algorithm
*
* verification-helper: PROBLEM https://judge.yosupo.jp/problem/bipartitematching
*/
#include <iostream>
#line 1 "include/emthrm/graph/flow/matching/hopcroft-karp_algorithm.hpp"
#include <algorithm>
#include <queue>
#include <vector>
namespace emthrm {
struct HopcroftKarp {
std::vector<int> match;
explicit HopcroftKarp(const int left, const int right)
: match(left + right, -1), left(left), t(0), level(left),
is_used(left, -1), graph(left) {}
void add_edge(const int u, const int v) {
graph[u].emplace_back(left + v);
}
int solve() {
int res = 0;
while (true) {
std::fill(level.begin(), level.end(), -1);
std::queue<int> que;
for (int i = 0; i < left; ++i) {
if (match[i] == -1) {
que.emplace(i);
level[i] = 0;
}
}
while (!que.empty()) {
const int ver = que.front();
que.pop();
for (const int dst : graph[ver]) {
if (match[dst] != -1 && level[match[dst]] == -1) {
level[match[dst]] = level[ver] + 1;
que.emplace(match[dst]);
}
}
}
int tmp = 0;
for (int i = 0; i < left; ++i) {
if (match[i] == -1) {
tmp += dfs(i);
++t;
}
}
if (tmp == 0) break;
res += tmp;
}
return res;
}
private:
const int left;
int t;
std::vector<int> level, is_used;
std::vector<std::vector<int>> graph;
bool dfs(const int ver) {
is_used[ver] = t;
for (const int dst : graph[ver]) {
const int m = match[dst];
if (m == -1 || (is_used[m] < t && level[m] == level[ver] + 1 && dfs(m))) {
is_used[ver] = t;
match[ver] = dst;
match[dst] = ver;
return true;
}
}
return false;
}
};
} // namespace emthrm
#line 10 "test/graph/flow/matching/hopcroft-karp_algorithm.test.cpp"
int main() {
int l, r, m;
std::cin >> l >> r >> m;
emthrm::HopcroftKarp hopcroft_karp(l, r);
while (m--) {
int a, b;
std::cin >> a >> b;
hopcroft_karp.add_edge(a, b);
}
std::cout << hopcroft_karp.solve() << '\n';
for (int i = 0; i < l; ++i) {
if (hopcroft_karp.match[i] != -1) {
std::cout << i << ' ' << hopcroft_karp.match[i] - l << '\n';
}
}
return 0;
}