general_matching.hpp¶
一般无向图的最大匹配：选出尽可能多条互不共用端点的边，返回数量和每点的配偶；支持奇环，用缩花处理。
Complexity: Time: \(O(V + E + V E \log (V + 1))\). Space: \(O(V + E)\).
Source: Library Checker
AC 记录：general_matching。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(V + E + V E log(V + 1)). Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
namespace general_matching_internal {
// Gabow's Edmonds search.
struct solver {
int n, root = -1;
std::vector<std::size_t> off;
std::vector<int> adj, mate, outer, parent, queue;
std::vector<std::pair<int, int>> link;
solver(int n_, const std::vector<std::pair<int, int>> &es)
: n(n_), off(std::size_t(n) + 1), mate(n, -1), outer(n, -1),
parent(n), link(n) {
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u != v) {
++off[u];
++off[v];
}
}
for (int u = 0; u < n; ++u) {
off[u + 1] += off[u];
}
adj.resize(off[n]);
// Reverse filling preserves input order within every adjacency row.
for (std::size_t i = es.size(); i-- > 0;) {
auto [u, v] = es[i];
if (u != v) {
adj[--off[u]] = v;
adj[--off[v]] = u;
}
}
queue.reserve(n);
}
// First nonouter vertex on the alternating path, or -1 at the root.
// Contractions are evaluated lazily, with iterative path compression.
int group(int x) {
int r = x;
while (parent[r] != -1 && outer[parent[r]] == root) {
r = parent[r];
}
int base = parent[r];
while (x != r) {
int next = parent[x];
parent[x] = base;
x = next;
}
return base;
}
void rematch(int x, int y) {
int d = mate[x];
mate[x] = y;
if (d == -1 || mate[d] != x) return;
auto [a, b] = link[x];
if (b == -1) {
mate[d] = a;
rematch(a, d);
} else {
rematch(a, b);
rematch(b, a);
}
}
bool augment() {
// Each unmatched root is searched at most once: its ID is the timestamp.
outer[root] = root;
parent[root] = -1;
link[root] = {-1, -1};
queue.clear();
queue.push_back(root);
for (std::size_t head = 0; head < queue.size(); ++head) {
int a = queue[head];
for (std::size_t i = off[a]; i < off[a + 1]; ++i) {
int b = adj[i];
if (b == root) {
continue;
}
if (mate[b] == -1) {
mate[b] = a;
rematch(a, b);
return true;
}
if (outer[b] == root) {
int x = group(a), y = group(b);
if (x == y) {
continue;
}
int z = -1;
while (x != -1 || y != -1) {
if (y != -1) {
std::swap(x, y);
}
if (link[x] == std::pair{a, b}) {
z = x;
break;
}
link[x] = {a, b};
x = group(link[mate[x]].first);
}
for (int v : {group(a), group(b)}) {
while (v != z) {
queue.push_back(v);
outer[v] = root;
parent[v] = z;
v = group(link[mate[v]].first);
}
}
} else if (outer[mate[b]] != root) {
int v = mate[b];
outer[v] = root;
link[b] = {-1, -1};
link[v] = {a, -1};
parent[v] = b;
queue.push_back(v);
}
}
}
return false;
}
std::pair<int, std::vector<int>> run() {
int size = 0;
// Any initial matching is valid; greedily take length-one augmentations.
for (int a = 0; a < n; ++a) {
if (mate[a] != -1) {
continue;
}
for (std::size_t i = off[a]; i < off[a + 1]; ++i) {
int b = adj[i];
if (mate[b] == -1) {
mate[a] = b;
mate[b] = a;
++size;
break;
}
}
}
for (root = 0; root < n; ++root) {
if (mate[root] == -1 && off[root] != off[root + 1] && augment()) {
++size;
}
}
return {size, std::move(mate)};
}
};
} // namespace general_matching_internal
/// @brief Maximum-cardinality matching in a general undirected multigraph.
/// Require n>=0 and endpoints in [0,n); self-loops are ignored and parallel
/// edges are allowed. Inputs are unchanged. Return (number of matched pairs,
/// mate of each vertex), with -1 for unmatched vertices. Any maximum matching
/// may be returned; it need not be lexicographically minimal. Blossom rematching uses recursion.
inline std::pair<int, std::vector<int>>
maximum_matching(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
return general_matching_internal::solver(n, es).run();
}
} // namespace noya
// NOYA_GENERAL_MATCHING_HPP
#ifndef NOYA_GENERAL_MATCHING_HPP
#define NOYA_GENERAL_MATCHING_HPP 1
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(V + E + V E log(V + 1)). Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
namespace general_matching_internal {
// Gabow's Edmonds search.
struct solver {
int n, root = -1;
std::vector<std::size_t> off;
std::vector<int> adj, mate, outer, parent, queue;
std::vector<std::pair<int, int>> link;
solver(int n_, const std::vector<std::pair<int, int>> &es)
: n(n_), off(std::size_t(n) + 1), mate(n, -1), outer(n, -1),
parent(n), link(n) {
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u != v) {
++off[u];
++off[v];
}
}
for (int u = 0; u < n; ++u) {
off[u + 1] += off[u];
}
adj.resize(off[n]);
// Reverse filling preserves input order within every adjacency row.
for (std::size_t i = es.size(); i-- > 0;) {
auto [u, v] = es[i];
if (u != v) {
adj[--off[u]] = v;
adj[--off[v]] = u;
}
}
queue.reserve(n);
}
// First nonouter vertex on the alternating path, or -1 at the root.
// Contractions are evaluated lazily, with iterative path compression.
int group(int x) {
int r = x;
while (parent[r] != -1 && outer[parent[r]] == root) {
r = parent[r];
}
int base = parent[r];
while (x != r) {
int next = parent[x];
parent[x] = base;
x = next;
}
return base;
}
void rematch(int x, int y) {
int d = mate[x];
mate[x] = y;
if (d == -1 || mate[d] != x) return;
auto [a, b] = link[x];
if (b == -1) {
mate[d] = a;
rematch(a, d);
} else {
rematch(a, b);
rematch(b, a);
}
}
bool augment() {
// Each unmatched root is searched at most once: its ID is the timestamp.
outer[root] = root;
parent[root] = -1;
link[root] = {-1, -1};
queue.clear();
queue.push_back(root);
for (std::size_t head = 0; head < queue.size(); ++head) {
int a = queue[head];
for (std::size_t i = off[a]; i < off[a + 1]; ++i) {
int b = adj[i];
if (b == root) {
continue;
}
if (mate[b] == -1) {
mate[b] = a;
rematch(a, b);
return true;
}
if (outer[b] == root) {
int x = group(a), y = group(b);
if (x == y) {
continue;
}
int z = -1;
while (x != -1 || y != -1) {
if (y != -1) {
std::swap(x, y);
}
if (link[x] == std::pair{a, b}) {
z = x;
break;
}
link[x] = {a, b};
x = group(link[mate[x]].first);
}
for (int v : {group(a), group(b)}) {
while (v != z) {
queue.push_back(v);
outer[v] = root;
parent[v] = z;
v = group(link[mate[v]].first);
}
}
} else if (outer[mate[b]] != root) {
int v = mate[b];
outer[v] = root;
link[b] = {-1, -1};
link[v] = {a, -1};
parent[v] = b;
queue.push_back(v);
}
}
}
return false;
}
std::pair<int, std::vector<int>> run() {
int size = 0;
// Any initial matching is valid; greedily take length-one augmentations.
for (int a = 0; a < n; ++a) {
if (mate[a] != -1) {
continue;
}
for (std::size_t i = off[a]; i < off[a + 1]; ++i) {
int b = adj[i];
if (mate[b] == -1) {
mate[a] = b;
mate[b] = a;
++size;
break;
}
}
}
for (root = 0; root < n; ++root) {
if (mate[root] == -1 && off[root] != off[root + 1] && augment()) {
++size;
}
}
return {size, std::move(mate)};
}
};
} // namespace general_matching_internal
/// @brief Maximum-cardinality matching in a general undirected multigraph.
/// Require n>=0 and endpoints in [0,n); self-loops are ignored and parallel
/// edges are allowed. Inputs are unchanged. Return (number of matched pairs,
/// mate of each vertex), with -1 for unmatched vertices. Any maximum matching
/// may be returned; it need not be lexicographically minimal. Blossom rematching uses recursion.
inline std::pair<int, std::vector<int>>
maximum_matching(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
return general_matching_internal::solver(n, es).run();
}
} // namespace noya
#endif // NOYA_GENERAL_MATCHING_HPP
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(V + E + V E log(V + 1)). Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
namespace general_matching_internal {
// Gabow's Edmonds search.
struct solver {
int n, root = -1;
std::vector<std::size_t> off;
std::vector<int> adj, mate, outer, parent, queue;
std::vector<std::pair<int, int>> link;
solver(int n_, const std::vector<std::pair<int, int>> &es)
: n(n_), off(std::size_t(n) + 1), mate(n, -1), outer(n, -1),
parent(n), link(n) {
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u != v) {
++off[u];
++off[v];
}
}
for (int u = 0; u < n; ++u) {
off[u + 1] += off[u];
}
adj.resize(off[n]);
// Reverse filling preserves input order within every adjacency row.
for (std::size_t i = es.size(); i-- > 0;) {
auto [u, v] = es[i];
if (u != v) {
adj[--off[u]] = v;
adj[--off[v]] = u;
}
}
queue.reserve(n);
}
// First nonouter vertex on the alternating path, or -1 at the root.
// Contractions are evaluated lazily, with iterative path compression.
int group(int x) {
int r = x;
while (parent[r] != -1 && outer[parent[r]] == root) {
r = parent[r];
}
int base = parent[r];
while (x != r) {
int next = parent[x];
parent[x] = base;
x = next;
}
return base;
}
void rematch(int x, int y) {
int d = mate[x];
mate[x] = y;
if (d == -1 || mate[d] != x) return;
auto [a, b] = link[x];
if (b == -1) {
mate[d] = a;
rematch(a, d);
} else {
rematch(a, b);
rematch(b, a);
}
}
bool augment() {
// Each unmatched root is searched at most once: its ID is the timestamp.
outer[root] = root;
parent[root] = -1;
link[root] = {-1, -1};
queue.clear();
queue.push_back(root);
for (std::size_t head = 0; head < queue.size(); ++head) {
int a = queue[head];
for (std::size_t i = off[a]; i < off[a + 1]; ++i) {
int b = adj[i];
if (b == root) {
continue;
}
if (mate[b] == -1) {
mate[b] = a;
rematch(a, b);
return true;
}
if (outer[b] == root) {
int x = group(a), y = group(b);
if (x == y) {
continue;
}
int z = -1;
while (x != -1 || y != -1) {
if (y != -1) {
std::swap(x, y);
}
if (link[x] == std::pair{a, b}) {
z = x;
break;
}
link[x] = {a, b};
x = group(link[mate[x]].first);
}
for (int v : {group(a), group(b)}) {
while (v != z) {
queue.push_back(v);
outer[v] = root;
parent[v] = z;
v = group(link[mate[v]].first);
}
}
} else if (outer[mate[b]] != root) {
int v = mate[b];
outer[v] = root;
link[b] = {-1, -1};
link[v] = {a, -1};
parent[v] = b;
queue.push_back(v);
}
}
}
return false;
}
std::pair<int, std::vector<int>> run() {
int size = 0;
// Any initial matching is valid; greedily take length-one augmentations.
for (int a = 0; a < n; ++a) {
if (mate[a] != -1) {
continue;
}
for (std::size_t i = off[a]; i < off[a + 1]; ++i) {
int b = adj[i];
if (mate[b] == -1) {
mate[a] = b;
mate[b] = a;
++size;
break;
}
}
}
for (root = 0; root < n; ++root) {
if (mate[root] == -1 && off[root] != off[root + 1] && augment()) {
++size;
}
}
return {size, std::move(mate)};
}
};
} // namespace general_matching_internal
/// @brief Maximum-cardinality matching in a general undirected multigraph.
/// Require n>=0 and endpoints in [0,n); self-loops are ignored and parallel
/// edges are allowed. Inputs are unchanged. Return (number of matched pairs,
/// mate of each vertex), with -1 for unmatched vertices. Any maximum matching
/// may be returned; it need not be lexicographically minimal. Blossom rematching uses recursion.
inline std::pair<int, std::vector<int>>
maximum_matching(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
return general_matching_internal::solver(n, es).run();
}
} // namespace noya
// NOYA_GENERAL_MATCHING_HPP