general_matching.hpp¶
Maximum matching in a general undirected graph in O(n^3).
Verified by general_matching.
用带花树求一般无向图最大基数匹配；适合图不保证二分的配对问题。
Implementation¶
#ifndef NOYA_GENERAL_MATCHING_HPP
#define NOYA_GENERAL_MATCHING_HPP 1
/// @complexity Time: O(V^3).
/// Space: O(V^2).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace general_matching_internal {
struct solver {
int n;
std::vector<std::vector<int>> graph;
std::vector<int> match, parent, base;
std::vector<bool> used, blossom;
solver(int n_, const std::vector<std::pair<int, int>> &edges)
: n(n_), graph(n), match(n, -1), parent(n), base(n), used(n), blossom(n) {
assert(n >= 0);
for (auto [u, v] : edges) {
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (u != v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
}
}
int least_common_ancestor(int first, int second) {
std::vector<bool> on_path(n);
while (true) {
first = base[first];
on_path[first] = true;
if (match[first] == -1) {
break;
}
first = parent[match[first]];
}
while (true) {
second = base[second];
if (on_path[second]) {
return second;
}
second = parent[match[second]];
}
}
void mark_path(int vertex, int common_base, int child) {
while (base[vertex] != common_base) {
blossom[base[vertex]] = true;
blossom[base[match[vertex]]] = true;
parent[vertex] = child;
child = match[vertex];
vertex = parent[match[vertex]];
}
}
bool augment_from(int root) {
std::fill(used.begin(), used.end(), false);
std::fill(parent.begin(), parent.end(), -1);
std::iota(base.begin(), base.end(), 0);
std::queue<int> queue;
queue.push(root);
used[root] = true;
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
for (int to : graph[vertex]) {
if (base[vertex] == base[to] || match[vertex] == to) {
continue;
}
if (to == root || (match[to] != -1 && parent[match[to]] != -1)) {
int common_base = least_common_ancestor(vertex, to);
std::fill(blossom.begin(), blossom.end(), false);
mark_path(vertex, common_base, to);
mark_path(to, common_base, vertex);
for (int i = 0; i < n; i++) {
if (!blossom[base[i]]) {
continue;
}
base[i] = common_base;
if (!used[i]) {
used[i] = true;
queue.push(i);
}
}
} else if (parent[to] == -1) {
parent[to] = vertex;
if (match[to] == -1) {
for (int current = to; current != -1;) {
int previous = parent[current];
int next = previous == -1 ? -1 : match[previous];
match[current] = previous;
if (previous != -1) {
match[previous] = current;
}
current = next;
}
return true;
}
to = match[to];
used[to] = true;
queue.push(to);
}
}
}
return false;
}
std::pair<int, std::vector<int>> run() {
int size = 0;
for (int vertex = 0; vertex < n; vertex++) {
if (match[vertex] == -1 && augment_from(vertex)) {
size++;
}
}
return {size, match};
}
};
} // namespace general_matching_internal
/// @brief Maximum matching in a general undirected graph in O(n^3).
/// @return (matching size, mate of every vertex), with -1 for unmatched
/// vertices.
inline std::pair<int, std::vector<int>>
maximum_matching(int n, const std::vector<std::pair<int, int>> &edges) {
return general_matching_internal::solver(n, edges).run();
}
} // namespace noya
#endif // NOYA_GENERAL_MATCHING_HPP
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(V^3).
/// Space: O(V^2).
namespace noya {
namespace general_matching_internal {
struct solver {
int n;
std::vector<std::vector<int>> graph;
std::vector<int> match, parent, base;
std::vector<bool> used, blossom;
solver(int n_, const std::vector<std::pair<int, int>> &edges)
: n(n_), graph(n), match(n, -1), parent(n), base(n), used(n), blossom(n) {
assert(n >= 0);
for (auto [u, v] : edges) {
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (u != v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
}
}
int least_common_ancestor(int first, int second) {
std::vector<bool> on_path(n);
while (true) {
first = base[first];
on_path[first] = true;
if (match[first] == -1) {
break;
}
first = parent[match[first]];
}
while (true) {
second = base[second];
if (on_path[second]) {
return second;
}
second = parent[match[second]];
}
}
void mark_path(int vertex, int common_base, int child) {
while (base[vertex] != common_base) {
blossom[base[vertex]] = true;
blossom[base[match[vertex]]] = true;
parent[vertex] = child;
child = match[vertex];
vertex = parent[match[vertex]];
}
}
bool augment_from(int root) {
std::fill(used.begin(), used.end(), false);
std::fill(parent.begin(), parent.end(), -1);
std::iota(base.begin(), base.end(), 0);
std::queue<int> queue;
queue.push(root);
used[root] = true;
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
for (int to : graph[vertex]) {
if (base[vertex] == base[to] || match[vertex] == to) {
continue;
}
if (to == root || (match[to] != -1 && parent[match[to]] != -1)) {
int common_base = least_common_ancestor(vertex, to);
std::fill(blossom.begin(), blossom.end(), false);
mark_path(vertex, common_base, to);
mark_path(to, common_base, vertex);
for (int i = 0; i < n; i++) {
if (!blossom[base[i]]) {
continue;
}
base[i] = common_base;
if (!used[i]) {
used[i] = true;
queue.push(i);
}
}
} else if (parent[to] == -1) {
parent[to] = vertex;
if (match[to] == -1) {
for (int current = to; current != -1;) {
int previous = parent[current];
int next = previous == -1 ? -1 : match[previous];
match[current] = previous;
if (previous != -1) {
match[previous] = current;
}
current = next;
}
return true;
}
to = match[to];
used[to] = true;
queue.push(to);
}
}
}
return false;
}
std::pair<int, std::vector<int>> run() {
int size = 0;
for (int vertex = 0; vertex < n; vertex++) {
if (match[vertex] == -1 && augment_from(vertex)) {
size++;
}
}
return {size, match};
}
};
} // namespace general_matching_internal
/// @brief Maximum matching in a general undirected graph in O(n^3).
/// @return (matching size, mate of every vertex), with -1 for unmatched
/// vertices.
inline std::pair<int, std::vector<int>>
maximum_matching(int n, const std::vector<std::pair<int, int>> &edges) {
return general_matching_internal::solver(n, edges).run();
}
} // namespace noya