test/graph/general-matching/yosupo-Matching-on-General-Graph.test.cpp

• View this file on GitHub
• Last update: 2023-05-29 14:59:47+08:00
• Problem: https://judge.yosupo.jp/problem/general_matching

Depends on

• library/graph/general-matching.hpp

Code

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

#include <iostream>
#include "../../../library/graph/general-matching.hpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	general_matching solver(n);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		solver.add_edge(u, v);
	}
	cout << solver.solve() << "\n";
	for(int i = 0; i < n; i++) {
		if(i < solver.match(i)) {
			cout << i << " " << solver.match(i) << "\n";
		}
	}
	return 0;
}

#line 1 "test/graph/general-matching/yosupo-Matching-on-General-Graph.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/general_matching"

#include <iostream>
#line 2 "library/graph/general-matching.hpp"
#include <vector>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <algorithm>

namespace felix {

struct general_matching {
public:
	general_matching() : n(0) {}
	explicit general_matching(int n) : n(n), g(n, -1), mate(n, -1), vis(n, false) {}

	void add_edge(int a, int b) {
		edges.emplace_back(b, g[a]);
		g[a] = (int) edges.size() - 1;
		edges.emplace_back(a, g[b]);
		g[b] = (int) edges.size() - 1;
	}

	bool dfs(int u) {
		if(vis[u]) {
			return false;
		}
		vis[u] = true;
		for(int ei = g[u]; ei != -1; ) {
			auto [x, y] = edges[ei]; ei = y;
			if(mate[x] == -1) {
				mate[u] = x;
				mate[x] = u;
				return true;
			}
		}
		for(int ei = g[u]; ei != -1; ) {
			auto [x, y] = edges[ei]; ei = y;
			int nu = mate[x];
			mate[u] = x;
			mate[x] = u;
			mate[nu] = -1;
			if(dfs(nu)) {
				return true;
			}
			mate[nu] = x;
			mate[x] = nu;
			mate[u] = -1;
		}
		return false;
	}

	int solve() {
		static std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
		std::vector<int> order(n);
		std::iota(order.begin(), order.end(), 0);
		int ans = 0;
		for(int it = 0; it < 100; ++it) {
			std::shuffle(order.begin(), order.end(), rng);
			std::fill(vis.begin(), vis.end(), false);
			for(auto u : order) {
				if(mate[u] == -1) {
					ans += dfs(u);
				}
			}
		}
		return ans;
	}

	int match(int u) const { return mate[u]; }

private:
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> g, mate;
	std::vector<bool> vis;
};

} // namespace felix
#line 5 "test/graph/general-matching/yosupo-Matching-on-General-Graph.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	general_matching solver(n);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		solver.add_edge(u, v);
	}
	cout << solver.solve() << "\n";
	for(int i = 0; i < n; i++) {
		if(i < solver.match(i)) {
			cout << i << " " << solver.match(i) << "\n";
		}
	}
	return 0;
}

Back to top page