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

• View this file on GitHub
• Last update: 2021-03-14 12:24:54+09:00
• Include: #include "GraphTheory/BipartiteMatching.hpp"
• Link: https://tkmst201.github.io/Library/GraphTheory/BipartiteMatching.hpp

概要

二部グラフ上の最大マッチングを求めます。
計算量は、$2$ つの頂点集合をそれぞれ $S$, $T$ 、辺の数を $M$ として $\mathcal{O}(\min(|S|, |T|) M)$ です。
実際はかなり高速です。

• BipartiteMatching(int x, int y)
  • $\Theta(x + y)$ $|S| = x, |T| = y$ で初期化
• BipartiteMatching(int n)
  • $\Theta(n)$ $|S| = |T| = n$ で初期化
• void add_edge(int a, int b)
  • ならし $\Theta(1)$ $S$ の頂点 $a$ と $T$ の頂点 $b$ の間に辺を張る
• void build()
  • $\mathcal{O}(\min(|S|, |T|) M)$ $S, T$ の最大マッチングを求める
• int max_matching()
  • $\Theta(1)$ $S, T$ の最大マッチングでのマッチング数を返す
• std::vector<std::pair<int, int>> matching()
  • $\Theta(\min(|S|, |T|))$ $S, T$ の最大マッチングでのそれぞれのマッチングの組 ($S, T$ の順) を返す
• int matching_x(int k)
  • $\Theta(1)$ $S, T$ の最大マッチングでの $S$ の頂点 $k$ のマッチング先を返す
• int matching_y(int k)
  • $\Theta(1)$ $S, T$ の最大マッチングでの $T$ の頂点 $k$ のマッチング先を返す

コンストラクタ

以下、$2$ つの頂点集合をそれぞれ $S$, $T$ 、辺の数を $M$ とします。

---

BipartiteMatching(int x, int y)

$|S| = x, |T| = y$ で初期化します。

制約

• $0 \leq x, y$

計算量

• $\Theta(x + y)$

---

BipartiteMatching(int n)

$|S| = |T| = n$ で初期化します。

制約

• $0 \leq n$

計算量

• $\Theta(n)$

---

メンバ関数

void add_edge(int a, int b)

$S$ の頂点 $a$ と $T$ の頂点 $b$ の間に辺を張ります。

計算量

• ならし $\Theta(1)$

---

void build()

$S, T$ の最大マッチングを求めます。 必ず事前に呼んでください。

計算量

• $\mathcal{O}(\min(|S|, |T|) M)$

---

int max_matching()

$S, T$ の最大マッチングでのマッチング数を返します。

計算量

• $\Theta(1)$

std::vector<std::pair<int, int>> matching()

$S, T$ の最大マッチングでのそれぞれのマッチングの組 ($S, T$ の順) を返します。

計算量

• $\Theta(\min(|S|, |T|))$

---

int matching_x(int k)

$S, T$ の最大マッチングでの $S$ の頂点 $k$ のマッチング先を返します。 存在しなければ $-1$ を返します。

制約

• $0 \leq k < |S|$

計算量

• $\Theta(1)$

---

int matching_y(int k)

$S, T$ の最大マッチングでの $T$ の頂点 $k$ のマッチング先を返します。 存在しなければ $-1$ を返します。

制約

• $0 \leq k < |T|$

計算量

• $\Theta(1)$

---

使用例

#include <bits/stdc++.h>
#include "GraphTheory/BipartiteMatching.hpp"
using namespace std;

int main() {
	BipartiteMatching bm(3, 4);
	// S -> T
	// 0 -> 0 1
	// 1 -> 1
	// 2 -> 1 3
	bm.add_edge(0, 0);
	bm.add_edge(0, 1);
	bm.add_edge(1, 1);
	bm.add_edge(2, 1);
	bm.add_edge(2, 3);
	bm.build(); // 必ず呼ぶ
	
	cout << "max_matching() = " << bm.max_matching() << endl; // 3
	/*
		matching : 0 - 0
		matching : 1 - 1
		matching : 2 - 3
	*/
	for (auto [x, y] : bm.matching()) cout << "matching : " << x << " - " << y << endl;
	
	/*
		S: x = 0 - 0
		S: x = 1 - 1
		S: x = 2 - 3
		
		T: y = 0 - 0
		T: y = 1 - 1
		T: y = 2 - -1
		T: y = 3 - 2
	*/
	for (int i = 0; i < 3; ++i) cout << "S: x = " << i << " - " << bm.matching_x(i) << endl;
	for (int i = 0; i < 4; ++i) cout << "T: y = " << i << " - " << bm.matching_y(i) << endl;
}

参考

2021/03/13: https://manabitimes.jp/math/1147
2020/03/05: https://ikatakos.com/pot/programming_algorithm/graph_theory/bipartite_matching
2020/08/26: https://snuke.hatenablog.com/entry/2019/05/07/013609

Verified with

• Test/BipartiteMatching.test.cpp

Code

#ifndef INCLUDE_GUARD_BIPARTITE_MATCHING_HPP
#define INCLUDE_GUARD_BIPARTITE_MATCHING_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];
	}
};

#endif // INCLUDE_GUARD_BIPARTITE_MATCHING_HPP

#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];
	}
};

Back to top page