Test/BipartiteMatching.test.cpp

• View this file on GitHub
• Last update: 2021-03-14 12:24:54+09:00
• Problem: https://judge.yosupo.jp/problem/bipartitematching

Depends on

• 二部マッチング (GraphTheory/BipartiteMatching.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"

#include "GraphTheory/BipartiteMatching.hpp"

#include <cstdio>
#include <map>

int main() {
	int L, R, M;
	scanf("%d %d %d", &L, &R, &M);
	
	BipartiteMatching bm(L, R);
	for (int i = 0; i < M; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		bm.add_edge(a, b);
	}
	bm.build();
	
	printf("%d\n", bm.max_matching());
	
	std::map<int, int> mtl, mtr;
	for (auto [a, b] : bm.matching()) {
		printf("%d %d\n", a, b);
		mtl[a] = b;
		mtr[b] = a;
	}
	
	// [match_*] test

	for (int i = 0; i < L; ++i) assert(mtl.count(i) ? mtl[i] == bm.matching_x(i) : -1);
	for (int i = 0; i < R; ++i) assert(mtr.count(i) ? mtr[i] == bm.matching_y(i) : -1);
}

#line 1 "Test/BipartiteMatching.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"

#line 1 "GraphTheory/BipartiteMatching.hpp"



#include <vector>
#include <cassert>
#include <utility>
#include <queue>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/BipartiteMatching.hpp
 */
struct BipartiteMatching {
private:
	using Graph = std::vector<std::vector<int>>;
	Graph g;
	int x, y;
	bool isswap;
	int max_maching_;
	std::vector<int> match_x, match_y;
	bool isbuilt = false;
	
public:
	BipartiteMatching(int x, int y)
		: g(std::min(x, y)), x(std::min(x, y)), y(std::max(x, y)), isswap(x > y) {}
	
	BipartiteMatching(int n) : BipartiteMatching(n, n) {}
	
	void add_edge(int a, int b) {
		if (isswap) std::swap(a, b);
		assert(0 <= a && a < x);
		assert(0 <= b && b < y);
		g[a].emplace_back(b);
		isbuilt = false;
	}
	
	void build() {
		match_y.assign(y, -1);
		match_x.assign(x, -1);
		max_maching_ = 0;
		int c = 1;
		std::vector<int> visited(x, 0);
		bool update = false;
		auto dfs = [&](auto self, int u) -> bool {
			visited[u] = c;
			for (int v : g[u]) if (match_y[v] == -1) { match_y[v] = u; match_x[u] = v; return true; }
			for (int v : g[u]) if (visited[match_y[v]] >= 0 && visited[match_y[v]] != c && self(self, match_y[v])) { match_y[v] = u; match_x[u] = v; return true; }
			if (!update) visited[u] = -1;
			return false;
		};
		std::queue<int> que;
		for (int i = 0; i < x; ++i) {
			if (dfs(dfs, i)) ++max_maching_, update = true;
			else if (update) que.emplace(i);
		}
		while (!que.empty()) {
			++c;
			const int n = que.size();
			update = false;
			for (int i = 0; i < n; ++i) {
				const int u = que.front();
				que.pop();
				if (match_x[u] == -1 && visited[u] != c && dfs(dfs, u)) {
					++max_maching_;
					update = true;
				}
				else if (update) que.emplace(u);
			}
		}
		isbuilt = true;
	}
	
	int max_matching() const noexcept {
		assert(isbuilt);
		return max_maching_;
	}
	
	std::vector<std::pair<int, int>> matching() const {
		assert(isbuilt);
		std::vector<std::pair<int, int>> res;
		for (int i = 0; i < x; ++i) {
			if (match_x[i] == -1) continue;
			if (isswap) res.emplace_back(match_x[i], i);
			else res.emplace_back(i, match_x[i]);
		}
		return res;
	}
	
	int matching_x(int k) const noexcept {
		assert(isbuilt);
		assert(0 <= k && k < (isswap ? y : x));
		return isswap ? match_y[k] : match_x[k];
	}
	
	int matching_y(int k) const noexcept {
		assert(isbuilt);
		assert(0 <= k && k < (isswap ? x : y));
		return isswap ? match_x[k] : match_y[k];
	}
};


#line 4 "Test/BipartiteMatching.test.cpp"

#include <cstdio>
#include <map>

int main() {
	int L, R, M;
	scanf("%d %d %d", &L, &R, &M);
	
	BipartiteMatching bm(L, R);
	for (int i = 0; i < M; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		bm.add_edge(a, b);
	}
	bm.build();
	
	printf("%d\n", bm.max_matching());
	
	std::map<int, int> mtl, mtr;
	for (auto [a, b] : bm.matching()) {
		printf("%d %d\n", a, b);
		mtl[a] = b;
		mtr[b] = a;
	}
	
	// [match_*] test

	for (int i = 0; i < L; ++i) assert(mtl.count(i) ? mtl[i] == bm.matching_x(i) : -1);
	for (int i = 0; i < R; ++i) assert(mtr.count(i) ? mtr[i] == bm.matching_y(i) : -1);
}

Back to top page