bipartite_decomposition.hpp¶
把二分图的匹配结构分解成 Dulmage–Mendelsohn 块；用于刻画哪些顶点可被最大匹配覆盖。
Complexity: Time: O(E sqrt(V)) for matching/cover; DAG reductions add their constructed edges. Space: O(V + E).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(E sqrt(V)) for matching/cover; DAG reductions add their constructed edges.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
struct bipartite_decomposition_result {
std::vector<int> ml;
std::vector<int> mr;
std::vector<int> cvl;
std::vector<int> cvr;
std::vector<int> isl;
std::vector<int> isr;
bool ok = false;
std::vector<std::pair<int, int>> ec;
int matching_size() const {
return int(
std::count_if(ml.begin(), ml.end(), [](int val) { return val != -1; }));
}
};
/// @brief Hopcroft-Karp matching with Konig minimum vertex cover, maximum
/// independent set, and a minimum edge cover when the graph has no isolates.
inline bipartite_decomposition_result
bipartite_decomposition(int nl, int nr,
const std::vector<std::pair<int, int>> &es) {
assert(nl >= 0 && nr >= 0);
std::vector<std::vector<int>> g(nl);
std::vector<std::vector<int>> rg(nr);
for (auto [l, r] : es) {
assert(0 <= l && l < nl);
assert(0 <= r && r < nr);
g[l].push_back(r);
rg[r].push_back(l);
}
for (auto &adj : g) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
for (auto &adj : rg) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
bipartite_decomposition_result res;
res.ml.assign(nl, -1);
res.mr.assign(nr, -1);
std::vector<int> dis(nl);
while (true) {
std::queue<int> q;
std::fill(dis.begin(), dis.end(), -1);
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
dis[l] = 0;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int r : g[l]) {
int nxt = res.mr[r];
if (nxt != -1 && dis[nxt] == -1) {
dis[nxt] = dis[l] + 1;
q.push(nxt);
}
}
}
auto aug = [&](auto &self, int l) -> bool {
for (int r : g[l]) {
int nxt = res.mr[r];
if (nxt == -1 || (dis[nxt] == dis[l] + 1 && self(self, nxt))) {
res.ml[l] = r;
res.mr[r] = l;
return true;
}
}
dis[l] = -1;
return false;
};
int au1 = 0;
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
au1 += aug(aug, l);
}
}
if (au1 == 0) {
break;
}
}
std::vector<bool> rl(nl);
std::vector<bool> rr(nr);
std::queue<int> q;
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
rl[l] = true;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int r : g[l]) {
if (res.ml[l] == r || rr[r]) {
continue;
}
rr[r] = true;
int nxt = res.mr[r];
if (nxt != -1 && !rl[nxt]) {
rl[nxt] = true;
q.push(nxt);
}
}
}
for (int l = 0; l < nl; l++) {
if (rl[l]) {
res.isl.push_back(l);
} else {
res.cvl.push_back(l);
}
}
for (int r = 0; r < nr; r++) {
if (rr[r]) {
res.cvr.push_back(r);
} else {
res.isr.push_back(r);
}
}
res.ok = true;
for (int l = 0; l < nl; l++) {
res.ok &= !g[l].empty();
if (res.ml[l] != -1) {
res.ec.emplace_back(l, res.ml[l]);
}
}
for (int r = 0; r < nr; r++) {
res.ok &= !rg[r].empty();
}
if (res.ok) {
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
res.ec.emplace_back(l, g[l][0]);
}
}
for (int r = 0; r < nr; r++) {
if (res.mr[r] == -1) {
res.ec.emplace_back(rg[r][0], r);
}
}
} else {
res.ec.clear();
}
return res;
}
/// @brief Return a minimum vertex-disjoint directed path cover of a DAG using
/// bipartite matching; edges inside each returned path are original graph
/// edges.
inline std::vector<std::vector<int>>
minimum_dag_path_cover(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
std::vector<int> deg(n);
for (auto [v, to] : es) {
assert(0 <= v && v < n);
assert(0 <= to && to < n);
g[v].push_back(to);
deg[to]++;
}
std::queue<int> q;
for (int u = 0; u < n; u++) {
if (deg[u] == 0) {
q.push(u);
}
}
int cnt = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
cnt++;
for (int nxt : g[u]) {
if (--deg[nxt] == 0) {
q.push(nxt);
}
}
}
assert(cnt == n);
auto dec = bipartite_decomposition(n, n, es);
std::vector<std::vector<int>> pth;
for (int s = 0; s < n; s++) {
if (dec.mr[s] != -1) {
continue;
}
pth.emplace_back();
for (int u = s; u != -1; u = dec.ml[u]) {
pth.back().push_back(u);
}
}
return pth;
}
struct dag_order_decomposition_result {
std::vector<int> ac;
std::vector<std::vector<int>> cc;
};
/// @brief Maximum reachability antichain and minimum chain cover of a DAG via
/// transitive closure and Dilworth's theorem in O(n^3).
inline dag_order_decomposition_result
dag_order_decomposition(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<bool>> vis(n, std::vector<bool>(n));
std::vector<int> deg(n);
std::vector<std::vector<int>> g(n);
for (auto [v, to] : es) {
assert(0 <= v && v < n);
assert(0 <= to && to < n);
g[v].push_back(to);
deg[to]++;
vis[v][to] = true;
}
std::queue<int> q;
for (int u = 0; u < n; u++) {
if (deg[u] == 0) {
q.push(u);
}
}
std::vector<int> top;
while (!q.empty()) {
int u = q.front();
q.pop();
top.push_back(u);
for (int nxt : g[u]) {
if (--deg[nxt] == 0) {
q.push(nxt);
}
}
}
assert(int(top.size()) == n);
for (int mid : top) {
for (int v = 0; v < n; v++) {
if (vis[v][mid]) {
for (int to = 0; to < n; to++) {
vis[v][to] = vis[v][to] || vis[mid][to];
}
}
}
}
std::vector<std::pair<int, int>> cmp;
for (int v = 0; v < n; v++) {
for (int to = 0; to < n; to++) {
if (vis[v][to]) {
cmp.emplace_back(v, to);
}
}
}
auto dec = bipartite_decomposition(n, n, cmp);
std::vector<bool> cl(n), cr(n);
for (int u : dec.cvl) {
cl[u] = true;
}
for (int u : dec.cvr) {
cr[u] = true;
}
dag_order_decomposition_result res;
for (int u = 0; u < n; u++) {
if (!cl[u] && !cr[u]) {
res.ac.push_back(u);
}
}
for (int s = 0; s < n; s++) {
if (dec.mr[s] != -1) {
continue;
}
res.cc.emplace_back();
for (int u = s; u != -1; u = dec.ml[u]) {
res.cc.back().push_back(u);
}
}
return res;
}
} // namespace noya
#ifndef NOYA_BIPARTITE_DECOMPOSITION_HPP
#define NOYA_BIPARTITE_DECOMPOSITION_HPP 1
/// @complexity Time: O(E sqrt(V)) for matching/cover; DAG reductions add their constructed edges.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
struct bipartite_decomposition_result {
std::vector<int> ml;
std::vector<int> mr;
std::vector<int> cvl;
std::vector<int> cvr;
std::vector<int> isl;
std::vector<int> isr;
bool ok = false;
std::vector<std::pair<int, int>> ec;
int matching_size() const {
return int(
std::count_if(ml.begin(), ml.end(), [](int val) { return val != -1; }));
}
};
/// @brief Hopcroft-Karp matching with Konig minimum vertex cover, maximum
/// independent set, and a minimum edge cover when the graph has no isolates.
inline bipartite_decomposition_result
bipartite_decomposition(int nl, int nr,
const std::vector<std::pair<int, int>> &es) {
assert(nl >= 0 && nr >= 0);
std::vector<std::vector<int>> g(nl);
std::vector<std::vector<int>> rg(nr);
for (auto [l, r] : es) {
assert(0 <= l && l < nl);
assert(0 <= r && r < nr);
g[l].push_back(r);
rg[r].push_back(l);
}
for (auto &adj : g) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
for (auto &adj : rg) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
bipartite_decomposition_result res;
res.ml.assign(nl, -1);
res.mr.assign(nr, -1);
std::vector<int> dis(nl);
while (true) {
std::queue<int> q;
std::fill(dis.begin(), dis.end(), -1);
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
dis[l] = 0;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int r : g[l]) {
int nxt = res.mr[r];
if (nxt != -1 && dis[nxt] == -1) {
dis[nxt] = dis[l] + 1;
q.push(nxt);
}
}
}
auto aug = [&](auto &self, int l) -> bool {
for (int r : g[l]) {
int nxt = res.mr[r];
if (nxt == -1 || (dis[nxt] == dis[l] + 1 && self(self, nxt))) {
res.ml[l] = r;
res.mr[r] = l;
return true;
}
}
dis[l] = -1;
return false;
};
int au1 = 0;
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
au1 += aug(aug, l);
}
}
if (au1 == 0) {
break;
}
}
std::vector<bool> rl(nl);
std::vector<bool> rr(nr);
std::queue<int> q;
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
rl[l] = true;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int r : g[l]) {
if (res.ml[l] == r || rr[r]) {
continue;
}
rr[r] = true;
int nxt = res.mr[r];
if (nxt != -1 && !rl[nxt]) {
rl[nxt] = true;
q.push(nxt);
}
}
}
for (int l = 0; l < nl; l++) {
if (rl[l]) {
res.isl.push_back(l);
} else {
res.cvl.push_back(l);
}
}
for (int r = 0; r < nr; r++) {
if (rr[r]) {
res.cvr.push_back(r);
} else {
res.isr.push_back(r);
}
}
res.ok = true;
for (int l = 0; l < nl; l++) {
res.ok &= !g[l].empty();
if (res.ml[l] != -1) {
res.ec.emplace_back(l, res.ml[l]);
}
}
for (int r = 0; r < nr; r++) {
res.ok &= !rg[r].empty();
}
if (res.ok) {
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
res.ec.emplace_back(l, g[l][0]);
}
}
for (int r = 0; r < nr; r++) {
if (res.mr[r] == -1) {
res.ec.emplace_back(rg[r][0], r);
}
}
} else {
res.ec.clear();
}
return res;
}
/// @brief Return a minimum vertex-disjoint directed path cover of a DAG using
/// bipartite matching; edges inside each returned path are original graph
/// edges.
inline std::vector<std::vector<int>>
minimum_dag_path_cover(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
std::vector<int> deg(n);
for (auto [v, to] : es) {
assert(0 <= v && v < n);
assert(0 <= to && to < n);
g[v].push_back(to);
deg[to]++;
}
std::queue<int> q;
for (int u = 0; u < n; u++) {
if (deg[u] == 0) {
q.push(u);
}
}
int cnt = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
cnt++;
for (int nxt : g[u]) {
if (--deg[nxt] == 0) {
q.push(nxt);
}
}
}
assert(cnt == n);
auto dec = bipartite_decomposition(n, n, es);
std::vector<std::vector<int>> pth;
for (int s = 0; s < n; s++) {
if (dec.mr[s] != -1) {
continue;
}
pth.emplace_back();
for (int u = s; u != -1; u = dec.ml[u]) {
pth.back().push_back(u);
}
}
return pth;
}
struct dag_order_decomposition_result {
std::vector<int> ac;
std::vector<std::vector<int>> cc;
};
/// @brief Maximum reachability antichain and minimum chain cover of a DAG via
/// transitive closure and Dilworth's theorem in O(n^3).
inline dag_order_decomposition_result
dag_order_decomposition(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<bool>> vis(n, std::vector<bool>(n));
std::vector<int> deg(n);
std::vector<std::vector<int>> g(n);
for (auto [v, to] : es) {
assert(0 <= v && v < n);
assert(0 <= to && to < n);
g[v].push_back(to);
deg[to]++;
vis[v][to] = true;
}
std::queue<int> q;
for (int u = 0; u < n; u++) {
if (deg[u] == 0) {
q.push(u);
}
}
std::vector<int> top;
while (!q.empty()) {
int u = q.front();
q.pop();
top.push_back(u);
for (int nxt : g[u]) {
if (--deg[nxt] == 0) {
q.push(nxt);
}
}
}
assert(int(top.size()) == n);
for (int mid : top) {
for (int v = 0; v < n; v++) {
if (vis[v][mid]) {
for (int to = 0; to < n; to++) {
vis[v][to] = vis[v][to] || vis[mid][to];
}
}
}
}
std::vector<std::pair<int, int>> cmp;
for (int v = 0; v < n; v++) {
for (int to = 0; to < n; to++) {
if (vis[v][to]) {
cmp.emplace_back(v, to);
}
}
}
auto dec = bipartite_decomposition(n, n, cmp);
std::vector<bool> cl(n), cr(n);
for (int u : dec.cvl) {
cl[u] = true;
}
for (int u : dec.cvr) {
cr[u] = true;
}
dag_order_decomposition_result res;
for (int u = 0; u < n; u++) {
if (!cl[u] && !cr[u]) {
res.ac.push_back(u);
}
}
for (int s = 0; s < n; s++) {
if (dec.mr[s] != -1) {
continue;
}
res.cc.emplace_back();
for (int u = s; u != -1; u = dec.ml[u]) {
res.cc.back().push_back(u);
}
}
return res;
}
} // namespace noya
#endif // NOYA_BIPARTITE_DECOMPOSITION_HPP
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(E sqrt(V)) for matching/cover; DAG reductions add their constructed edges.
/// Space: O(V + E).
namespace noya {
struct bipartite_decomposition_result {
std::vector<int> ml;
std::vector<int> mr;
std::vector<int> cvl;
std::vector<int> cvr;
std::vector<int> isl;
std::vector<int> isr;
bool ok = false;
std::vector<std::pair<int, int>> ec;
int matching_size() const {
return int(
std::count_if(ml.begin(), ml.end(), [](int val) { return val != -1; }));
}
};
/// @brief Hopcroft-Karp matching with Konig minimum vertex cover, maximum
/// independent set, and a minimum edge cover when the graph has no isolates.
inline bipartite_decomposition_result
bipartite_decomposition(int nl, int nr,
const std::vector<std::pair<int, int>> &es) {
assert(nl >= 0 && nr >= 0);
std::vector<std::vector<int>> g(nl);
std::vector<std::vector<int>> rg(nr);
for (auto [l, r] : es) {
assert(0 <= l && l < nl);
assert(0 <= r && r < nr);
g[l].push_back(r);
rg[r].push_back(l);
}
for (auto &adj : g) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
for (auto &adj : rg) {
std::sort(adj.begin(), adj.end());
adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
}
bipartite_decomposition_result res;
res.ml.assign(nl, -1);
res.mr.assign(nr, -1);
std::vector<int> dis(nl);
while (true) {
std::queue<int> q;
std::fill(dis.begin(), dis.end(), -1);
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
dis[l] = 0;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int r : g[l]) {
int nxt = res.mr[r];
if (nxt != -1 && dis[nxt] == -1) {
dis[nxt] = dis[l] + 1;
q.push(nxt);
}
}
}
auto aug = [&](auto &self, int l) -> bool {
for (int r : g[l]) {
int nxt = res.mr[r];
if (nxt == -1 || (dis[nxt] == dis[l] + 1 && self(self, nxt))) {
res.ml[l] = r;
res.mr[r] = l;
return true;
}
}
dis[l] = -1;
return false;
};
int au1 = 0;
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
au1 += aug(aug, l);
}
}
if (au1 == 0) {
break;
}
}
std::vector<bool> rl(nl);
std::vector<bool> rr(nr);
std::queue<int> q;
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
rl[l] = true;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int r : g[l]) {
if (res.ml[l] == r || rr[r]) {
continue;
}
rr[r] = true;
int nxt = res.mr[r];
if (nxt != -1 && !rl[nxt]) {
rl[nxt] = true;
q.push(nxt);
}
}
}
for (int l = 0; l < nl; l++) {
if (rl[l]) {
res.isl.push_back(l);
} else {
res.cvl.push_back(l);
}
}
for (int r = 0; r < nr; r++) {
if (rr[r]) {
res.cvr.push_back(r);
} else {
res.isr.push_back(r);
}
}
res.ok = true;
for (int l = 0; l < nl; l++) {
res.ok &= !g[l].empty();
if (res.ml[l] != -1) {
res.ec.emplace_back(l, res.ml[l]);
}
}
for (int r = 0; r < nr; r++) {
res.ok &= !rg[r].empty();
}
if (res.ok) {
for (int l = 0; l < nl; l++) {
if (res.ml[l] == -1) {
res.ec.emplace_back(l, g[l][0]);
}
}
for (int r = 0; r < nr; r++) {
if (res.mr[r] == -1) {
res.ec.emplace_back(rg[r][0], r);
}
}
} else {
res.ec.clear();
}
return res;
}
/// @brief Return a minimum vertex-disjoint directed path cover of a DAG using
/// bipartite matching; edges inside each returned path are original graph
/// edges.
inline std::vector<std::vector<int>>
minimum_dag_path_cover(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<int>> g(n);
std::vector<int> deg(n);
for (auto [v, to] : es) {
assert(0 <= v && v < n);
assert(0 <= to && to < n);
g[v].push_back(to);
deg[to]++;
}
std::queue<int> q;
for (int u = 0; u < n; u++) {
if (deg[u] == 0) {
q.push(u);
}
}
int cnt = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
cnt++;
for (int nxt : g[u]) {
if (--deg[nxt] == 0) {
q.push(nxt);
}
}
}
assert(cnt == n);
auto dec = bipartite_decomposition(n, n, es);
std::vector<std::vector<int>> pth;
for (int s = 0; s < n; s++) {
if (dec.mr[s] != -1) {
continue;
}
pth.emplace_back();
for (int u = s; u != -1; u = dec.ml[u]) {
pth.back().push_back(u);
}
}
return pth;
}
struct dag_order_decomposition_result {
std::vector<int> ac;
std::vector<std::vector<int>> cc;
};
/// @brief Maximum reachability antichain and minimum chain cover of a DAG via
/// transitive closure and Dilworth's theorem in O(n^3).
inline dag_order_decomposition_result
dag_order_decomposition(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<bool>> vis(n, std::vector<bool>(n));
std::vector<int> deg(n);
std::vector<std::vector<int>> g(n);
for (auto [v, to] : es) {
assert(0 <= v && v < n);
assert(0 <= to && to < n);
g[v].push_back(to);
deg[to]++;
vis[v][to] = true;
}
std::queue<int> q;
for (int u = 0; u < n; u++) {
if (deg[u] == 0) {
q.push(u);
}
}
std::vector<int> top;
while (!q.empty()) {
int u = q.front();
q.pop();
top.push_back(u);
for (int nxt : g[u]) {
if (--deg[nxt] == 0) {
q.push(nxt);
}
}
}
assert(int(top.size()) == n);
for (int mid : top) {
for (int v = 0; v < n; v++) {
if (vis[v][mid]) {
for (int to = 0; to < n; to++) {
vis[v][to] = vis[v][to] || vis[mid][to];
}
}
}
}
std::vector<std::pair<int, int>> cmp;
for (int v = 0; v < n; v++) {
for (int to = 0; to < n; to++) {
if (vis[v][to]) {
cmp.emplace_back(v, to);
}
}
}
auto dec = bipartite_decomposition(n, n, cmp);
std::vector<bool> cl(n), cr(n);
for (int u : dec.cvl) {
cl[u] = true;
}
for (int u : dec.cvr) {
cr[u] = true;
}
dag_order_decomposition_result res;
for (int u = 0; u < n; u++) {
if (!cl[u] && !cr[u]) {
res.ac.push_back(u);
}
}
for (int s = 0; s < n; s++) {
if (dec.mr[s] != -1) {
continue;
}
res.cc.emplace_back();
for (int u = s; u != -1; u = dec.ml[u]) {
res.cc.back().push_back(u);
}
}
return res;
}
} // namespace noya