bipartite_decomposition.hpp¶
Hopcroft-Karp matching with Konig minimum vertex cover, maximum independent set, and a minimum edge cover when the graph has no isolates.
把二分图的匹配结构分解成 Dulmage–Mendelsohn 块；用于刻画哪些顶点可被最大匹配覆盖。
Implementation¶
#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> match_left;
std::vector<int> match_right;
std::vector<int> minimum_vertex_cover_left;
std::vector<int> minimum_vertex_cover_right;
std::vector<int> maximum_independent_set_left;
std::vector<int> maximum_independent_set_right;
bool edge_cover_exists = false;
std::vector<std::pair<int, int>> minimum_edge_cover;
int matching_size() const {
return int(std::count_if(match_left.begin(), match_left.end(),
[](int value) { return value != -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 left_size, int right_size,
const std::vector<std::pair<int, int>> &edges) {
assert(left_size >= 0 && right_size >= 0);
std::vector<std::vector<int>> graph(left_size);
std::vector<std::vector<int>> reverse_graph(right_size);
for (auto [left, right] : edges) {
assert(0 <= left && left < left_size);
assert(0 <= right && right < right_size);
graph[left].push_back(right);
reverse_graph[right].push_back(left);
}
for (auto &neighbors : graph) {
std::sort(neighbors.begin(), neighbors.end());
neighbors.erase(std::unique(neighbors.begin(), neighbors.end()),
neighbors.end());
}
for (auto &neighbors : reverse_graph) {
std::sort(neighbors.begin(), neighbors.end());
neighbors.erase(std::unique(neighbors.begin(), neighbors.end()),
neighbors.end());
}
bipartite_decomposition_result result;
result.match_left.assign(left_size, -1);
result.match_right.assign(right_size, -1);
std::vector<int> distance(left_size);
while (true) {
std::queue<int> queue;
std::fill(distance.begin(), distance.end(), -1);
for (int left = 0; left < left_size; left++) {
if (result.match_left[left] == -1) {
distance[left] = 0;
queue.push(left);
}
}
while (!queue.empty()) {
int left = queue.front();
queue.pop();
for (int right : graph[left]) {
int next = result.match_right[right];
if (next != -1 && distance[next] == -1) {
distance[next] = distance[left] + 1;
queue.push(next);
}
}
}
auto augment = [&](auto &self, int left) -> bool {
for (int right : graph[left]) {
int next = result.match_right[right];
if (next == -1 ||
(distance[next] == distance[left] + 1 && self(self, next))) {
result.match_left[left] = right;
result.match_right[right] = left;
return true;
}
}
distance[left] = -1;
return false;
};
int augmented = 0;
for (int left = 0; left < left_size; left++) {
if (result.match_left[left] == -1) {
augmented += augment(augment, left);
}
}
if (augmented == 0) {
break;
}
}
std::vector<bool> reachable_left(left_size);
std::vector<bool> reachable_right(right_size);
std::queue<int> queue;
for (int left = 0; left < left_size; left++) {
if (result.match_left[left] == -1) {
reachable_left[left] = true;
queue.push(left);
}
}
while (!queue.empty()) {
int left = queue.front();
queue.pop();
for (int right : graph[left]) {
if (result.match_left[left] == right || reachable_right[right]) {
continue;
}
reachable_right[right] = true;
int next = result.match_right[right];
if (next != -1 && !reachable_left[next]) {
reachable_left[next] = true;
queue.push(next);
}
}
}
for (int left = 0; left < left_size; left++) {
if (reachable_left[left]) {
result.maximum_independent_set_left.push_back(left);
} else {
result.minimum_vertex_cover_left.push_back(left);
}
}
for (int right = 0; right < right_size; right++) {
if (reachable_right[right]) {
result.minimum_vertex_cover_right.push_back(right);
} else {
result.maximum_independent_set_right.push_back(right);
}
}
result.edge_cover_exists = true;
for (int left = 0; left < left_size; left++) {
result.edge_cover_exists &= !graph[left].empty();
if (result.match_left[left] != -1) {
result.minimum_edge_cover.emplace_back(left, result.match_left[left]);
}
}
for (int right = 0; right < right_size; right++) {
result.edge_cover_exists &= !reverse_graph[right].empty();
}
if (result.edge_cover_exists) {
for (int left = 0; left < left_size; left++) {
if (result.match_left[left] == -1) {
result.minimum_edge_cover.emplace_back(left, graph[left][0]);
}
}
for (int right = 0; right < right_size; right++) {
if (result.match_right[right] == -1) {
result.minimum_edge_cover.emplace_back(reverse_graph[right][0], right);
}
}
} else {
result.minimum_edge_cover.clear();
}
return result;
}
/// @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>> &edges) {
assert(n >= 0);
std::vector<std::vector<int>> graph(n);
std::vector<int> indegree(n);
for (auto [from, to] : edges) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
graph[from].push_back(to);
indegree[to]++;
}
std::queue<int> queue;
for (int vertex = 0; vertex < n; vertex++) {
if (indegree[vertex] == 0) {
queue.push(vertex);
}
}
int processed = 0;
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
processed++;
for (int next : graph[vertex]) {
if (--indegree[next] == 0) {
queue.push(next);
}
}
}
assert(processed == n);
auto decomposition = bipartite_decomposition(n, n, edges);
std::vector<std::vector<int>> paths;
for (int start = 0; start < n; start++) {
if (decomposition.match_right[start] != -1) {
continue;
}
paths.emplace_back();
for (int vertex = start; vertex != -1;
vertex = decomposition.match_left[vertex]) {
paths.back().push_back(vertex);
}
}
return paths;
}
struct dag_order_decomposition_result {
std::vector<int> maximum_antichain;
std::vector<std::vector<int>> minimum_chain_cover;
};
/// @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>> &edges) {
assert(n >= 0);
std::vector<std::vector<bool>> reachable(n, std::vector<bool>(n));
std::vector<int> indegree(n);
std::vector<std::vector<int>> graph(n);
for (auto [from, to] : edges) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
graph[from].push_back(to);
indegree[to]++;
reachable[from][to] = true;
}
std::queue<int> queue;
for (int vertex = 0; vertex < n; vertex++) {
if (indegree[vertex] == 0) {
queue.push(vertex);
}
}
std::vector<int> topological;
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
topological.push_back(vertex);
for (int next : graph[vertex]) {
if (--indegree[next] == 0) {
queue.push(next);
}
}
}
assert(int(topological.size()) == n);
for (int middle : topological) {
for (int from = 0; from < n; from++) {
if (reachable[from][middle]) {
for (int to = 0; to < n; to++) {
reachable[from][to] = reachable[from][to] || reachable[middle][to];
}
}
}
}
std::vector<std::pair<int, int>> comparable;
for (int from = 0; from < n; from++) {
for (int to = 0; to < n; to++) {
if (reachable[from][to]) {
comparable.emplace_back(from, to);
}
}
}
auto decomposition = bipartite_decomposition(n, n, comparable);
std::vector<bool> cover_left(n), cover_right(n);
for (int vertex : decomposition.minimum_vertex_cover_left) {
cover_left[vertex] = true;
}
for (int vertex : decomposition.minimum_vertex_cover_right) {
cover_right[vertex] = true;
}
dag_order_decomposition_result result;
for (int vertex = 0; vertex < n; vertex++) {
if (!cover_left[vertex] && !cover_right[vertex]) {
result.maximum_antichain.push_back(vertex);
}
}
for (int start = 0; start < n; start++) {
if (decomposition.match_right[start] != -1) {
continue;
}
result.minimum_chain_cover.emplace_back();
for (int vertex = start; vertex != -1;
vertex = decomposition.match_left[vertex]) {
result.minimum_chain_cover.back().push_back(vertex);
}
}
return result;
}
} // 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> match_left;
std::vector<int> match_right;
std::vector<int> minimum_vertex_cover_left;
std::vector<int> minimum_vertex_cover_right;
std::vector<int> maximum_independent_set_left;
std::vector<int> maximum_independent_set_right;
bool edge_cover_exists = false;
std::vector<std::pair<int, int>> minimum_edge_cover;
int matching_size() const {
return int(std::count_if(match_left.begin(), match_left.end(),
[](int value) { return value != -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 left_size, int right_size,
const std::vector<std::pair<int, int>> &edges) {
assert(left_size >= 0 && right_size >= 0);
std::vector<std::vector<int>> graph(left_size);
std::vector<std::vector<int>> reverse_graph(right_size);
for (auto [left, right] : edges) {
assert(0 <= left && left < left_size);
assert(0 <= right && right < right_size);
graph[left].push_back(right);
reverse_graph[right].push_back(left);
}
for (auto &neighbors : graph) {
std::sort(neighbors.begin(), neighbors.end());
neighbors.erase(std::unique(neighbors.begin(), neighbors.end()),
neighbors.end());
}
for (auto &neighbors : reverse_graph) {
std::sort(neighbors.begin(), neighbors.end());
neighbors.erase(std::unique(neighbors.begin(), neighbors.end()),
neighbors.end());
}
bipartite_decomposition_result result;
result.match_left.assign(left_size, -1);
result.match_right.assign(right_size, -1);
std::vector<int> distance(left_size);
while (true) {
std::queue<int> queue;
std::fill(distance.begin(), distance.end(), -1);
for (int left = 0; left < left_size; left++) {
if (result.match_left[left] == -1) {
distance[left] = 0;
queue.push(left);
}
}
while (!queue.empty()) {
int left = queue.front();
queue.pop();
for (int right : graph[left]) {
int next = result.match_right[right];
if (next != -1 && distance[next] == -1) {
distance[next] = distance[left] + 1;
queue.push(next);
}
}
}
auto augment = [&](auto &self, int left) -> bool {
for (int right : graph[left]) {
int next = result.match_right[right];
if (next == -1 ||
(distance[next] == distance[left] + 1 && self(self, next))) {
result.match_left[left] = right;
result.match_right[right] = left;
return true;
}
}
distance[left] = -1;
return false;
};
int augmented = 0;
for (int left = 0; left < left_size; left++) {
if (result.match_left[left] == -1) {
augmented += augment(augment, left);
}
}
if (augmented == 0) {
break;
}
}
std::vector<bool> reachable_left(left_size);
std::vector<bool> reachable_right(right_size);
std::queue<int> queue;
for (int left = 0; left < left_size; left++) {
if (result.match_left[left] == -1) {
reachable_left[left] = true;
queue.push(left);
}
}
while (!queue.empty()) {
int left = queue.front();
queue.pop();
for (int right : graph[left]) {
if (result.match_left[left] == right || reachable_right[right]) {
continue;
}
reachable_right[right] = true;
int next = result.match_right[right];
if (next != -1 && !reachable_left[next]) {
reachable_left[next] = true;
queue.push(next);
}
}
}
for (int left = 0; left < left_size; left++) {
if (reachable_left[left]) {
result.maximum_independent_set_left.push_back(left);
} else {
result.minimum_vertex_cover_left.push_back(left);
}
}
for (int right = 0; right < right_size; right++) {
if (reachable_right[right]) {
result.minimum_vertex_cover_right.push_back(right);
} else {
result.maximum_independent_set_right.push_back(right);
}
}
result.edge_cover_exists = true;
for (int left = 0; left < left_size; left++) {
result.edge_cover_exists &= !graph[left].empty();
if (result.match_left[left] != -1) {
result.minimum_edge_cover.emplace_back(left, result.match_left[left]);
}
}
for (int right = 0; right < right_size; right++) {
result.edge_cover_exists &= !reverse_graph[right].empty();
}
if (result.edge_cover_exists) {
for (int left = 0; left < left_size; left++) {
if (result.match_left[left] == -1) {
result.minimum_edge_cover.emplace_back(left, graph[left][0]);
}
}
for (int right = 0; right < right_size; right++) {
if (result.match_right[right] == -1) {
result.minimum_edge_cover.emplace_back(reverse_graph[right][0], right);
}
}
} else {
result.minimum_edge_cover.clear();
}
return result;
}
/// @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>> &edges) {
assert(n >= 0);
std::vector<std::vector<int>> graph(n);
std::vector<int> indegree(n);
for (auto [from, to] : edges) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
graph[from].push_back(to);
indegree[to]++;
}
std::queue<int> queue;
for (int vertex = 0; vertex < n; vertex++) {
if (indegree[vertex] == 0) {
queue.push(vertex);
}
}
int processed = 0;
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
processed++;
for (int next : graph[vertex]) {
if (--indegree[next] == 0) {
queue.push(next);
}
}
}
assert(processed == n);
auto decomposition = bipartite_decomposition(n, n, edges);
std::vector<std::vector<int>> paths;
for (int start = 0; start < n; start++) {
if (decomposition.match_right[start] != -1) {
continue;
}
paths.emplace_back();
for (int vertex = start; vertex != -1;
vertex = decomposition.match_left[vertex]) {
paths.back().push_back(vertex);
}
}
return paths;
}
struct dag_order_decomposition_result {
std::vector<int> maximum_antichain;
std::vector<std::vector<int>> minimum_chain_cover;
};
/// @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>> &edges) {
assert(n >= 0);
std::vector<std::vector<bool>> reachable(n, std::vector<bool>(n));
std::vector<int> indegree(n);
std::vector<std::vector<int>> graph(n);
for (auto [from, to] : edges) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
graph[from].push_back(to);
indegree[to]++;
reachable[from][to] = true;
}
std::queue<int> queue;
for (int vertex = 0; vertex < n; vertex++) {
if (indegree[vertex] == 0) {
queue.push(vertex);
}
}
std::vector<int> topological;
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
topological.push_back(vertex);
for (int next : graph[vertex]) {
if (--indegree[next] == 0) {
queue.push(next);
}
}
}
assert(int(topological.size()) == n);
for (int middle : topological) {
for (int from = 0; from < n; from++) {
if (reachable[from][middle]) {
for (int to = 0; to < n; to++) {
reachable[from][to] = reachable[from][to] || reachable[middle][to];
}
}
}
}
std::vector<std::pair<int, int>> comparable;
for (int from = 0; from < n; from++) {
for (int to = 0; to < n; to++) {
if (reachable[from][to]) {
comparable.emplace_back(from, to);
}
}
}
auto decomposition = bipartite_decomposition(n, n, comparable);
std::vector<bool> cover_left(n), cover_right(n);
for (int vertex : decomposition.minimum_vertex_cover_left) {
cover_left[vertex] = true;
}
for (int vertex : decomposition.minimum_vertex_cover_right) {
cover_right[vertex] = true;
}
dag_order_decomposition_result result;
for (int vertex = 0; vertex < n; vertex++) {
if (!cover_left[vertex] && !cover_right[vertex]) {
result.maximum_antichain.push_back(vertex);
}
}
for (int start = 0; start < n; start++) {
if (decomposition.match_right[start] != -1) {
continue;
}
result.minimum_chain_cover.emplace_back();
for (int vertex = start; vertex != -1;
vertex = decomposition.match_left[vertex]) {
result.minimum_chain_cover.back().push_back(vertex);
}
}
return result;
}
} // namespace noya