bipartite_edge_coloring.hpp¶
用最大度种颜色给二分图的边染色，使同一顶点上的边颜色互异；按输入边顺序返回颜色，支持重边。
Complexity: Time: \(O(V + E \sqrt{S} \log (\Delta + 1))\); Space: \(O(V + E)\), where \(S\) is the larger contracted side and \(S \cdot \Delta \le 2 E\).
AC 记录：bipartite_edge_coloring。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E sqrt(S) log(Delta + 1)); Space: O(V + E),
/// where S is the larger contracted side and S * Delta <= 2E.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_edge_coloring_internal {
inline std::pair<std::vector<int>, int>
contract_vertices(const std::vector<int> °, int delta) {
// Counting-sort positive degrees, then pack consecutive vertices. Any two
// output groups have combined degree > delta, so padding needs at most 2E
// edges. Isolated vertices need no group.
std::vector<int> end(std::size_t(delta) + 1);
for (int d : deg) if (d) ++end[d];
for (int d = 1; d <= delta; ++d) end[d] += end[d - 1];
std::vector<int> order(end.back()), map(deg.size(), -1);
for (int u = int(deg.size()); u-- > 0;)
if (deg[u]) order[--end[deg[u]]] = u;
int group = 0, sum = 0;
for (int u : order) {
if (deg[u] > delta - sum) {
++group;
sum = 0;
}
map[u] = group;
sum += deg[u];
}
return {std::move(map), order.empty() ? 0 : group + 1};
}
struct edge_record {
int l, r, id1;
};
inline std::vector<int> perfect_matching(int n,
const std::vector<edge_record> &es,
const std::vector<int> &ids) {
// Every row has the same degree, so CSR offsets are just u * degree.
const std::size_t degree = ids.size() / n;
std::vector<int> adj(ids.size()), ml(n, -1), mr(n, -1), dist(n), queue;
std::vector<std::size_t> cur(n);
for (int u = 0; u < n; ++u) cur[u] = std::size_t(u) * degree;
for (int id : ids) adj[cur[es[id].l]++] = id;
int count = 0;
for (int u = 0; u < n; ++u) {
for (std::size_t i = std::size_t(u) * degree;
i < (std::size_t(u) + 1) * degree; ++i) {
int id = adj[i], r = es[id].r;
if (mr[r] == -1) {
ml[u] = mr[r] = id;
++count;
break;
}
}
}
queue.reserve(n);
while (count < n) {
std::fill(dist.begin(), dist.end(), -1);
queue.clear();
for (int u = 0; u < n; ++u) {
if (ml[u] == -1) {
dist[u] = 0;
queue.push_back(u);
}
}
int limit = -1;
for (std::size_t head = 0; head < queue.size(); ++head) {
int u = queue[head];
if (limit >= 0 && dist[u] >= limit) continue;
for (std::size_t i = std::size_t(u) * degree;
i < (std::size_t(u) + 1) * degree; ++i) {
int id = mr[es[adj[i]].r];
if (id == -1) {
limit = dist[u] + 1;
} else {
int v = es[id].l;
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
queue.push_back(v);
}
}
}
}
assert(limit > 0); // A nonempty regular bipartite graph has a perfect match.
for (int u = 0; u < n; ++u) cur[u] = std::size_t(u) * degree;
auto dfs = [&](auto &self, int u) -> bool {
while (cur[u] < (std::size_t(u) + 1) * degree) {
int id = adj[cur[u]++], old = mr[es[id].r];
int v = old == -1 ? -1 : es[old].l;
if (v == -1 ? dist[u] + 1 == limit
: dist[v] == dist[u] + 1 && dist[v] < limit && self(self, v)) {
ml[u] = mr[es[id].r] = id;
return true;
}
}
dist[u] = -1;
return false;
};
for (int u = 0; u < n; ++u)
if (ml[u] == -1 && dfs(dfs, u)) ++count;
}
return ml;
}
struct coloring_context {
int n;
const std::vector<edge_record> &es;
std::vector<int> &answer;
std::vector<unsigned char> used;
coloring_context(int n_, const std::vector<edge_record> &es_,
std::vector<int> &answer_)
: n(n_), es(es_), answer(answer_), used(es_.size()) {}
std::vector<int> split_even_regular(std::vector<int> &ids, int degree) {
std::vector<int> adj(2 * ids.size()), other;
std::vector<std::size_t> ptr(std::size_t(n) * 2);
for (std::size_t u = 0; u < ptr.size(); ++u) ptr[u] = u * degree;
for (int id : ids) {
used[id] = 0; // Reset only this subproblem, not the entire root graph.
adj[ptr[es[id].l]++] = id;
adj[ptr[std::size_t(n) + es[id].r]++] = id;
}
for (std::size_t u = 0; u < ptr.size(); ++u) ptr[u] = u * degree;
other.reserve(ids.size() / 2);
std::size_t count = 0;
for (std::size_t s = 0; s < ptr.size(); ++s) {
// A maximal trail in an even-degree graph closes at its start. Because
// the graph is bipartite, its length is even: alternate edges directly.
std::size_t u = s;
bool parity = false;
while (true) {
while (ptr[u] < (u + 1) * degree && used[adj[ptr[u]]]) ++ptr[u];
if (ptr[u] == (u + 1) * degree) break;
int id = adj[ptr[u]++];
used[id] = 1;
if (parity) other.push_back(id);
else ids[count++] = id;
parity = !parity;
u = u < std::size_t(n) ? std::size_t(n) + es[id].r : es[id].l;
}
assert(u == s && !parity);
}
assert(count == ids.size() / 2 && other.size() == count);
ids.resize(count);
return other;
}
void assign(const std::vector<int> &ids, int color) {
for (int id : ids)
if (es[id].id1 != -1) answer[es[id].id1] = color;
}
void solve(std::vector<int> ids, int degree, int offset = 0) {
assert(degree > 0 && ids.size() == std::size_t(n) * degree);
if (degree == 1) {
assign(ids, offset);
} else if (degree % 2 == 0) {
auto other = split_even_regular(ids, degree);
solve(std::move(ids), degree / 2, offset);
solve(std::move(other), degree / 2, offset + degree / 2);
} else {
auto matching = perfect_matching(n, es, ids);
assign(matching, offset);
std::size_t count = 0;
for (int id : ids)
if (matching[es[id].l] != id) ids[count++] = id;
ids.resize(count);
solve(std::move(ids), degree - 1, offset + 1);
}
}
};
} // namespace bipartite_edge_coloring_internal
/// @brief Color a bipartite multigraph optimally using colors [0, Delta).
/// Returns colors in input-edge order; duplicate edges are distinct. The input
/// is unchanged, but the optimal coloring is not canonical. Empty input gives
/// an empty result. Original and padded edge counts must fit in int.
inline std::vector<int>
bipartite_edge_coloring(int nl, int nr,
const std::vector<std::pair<int, int>> &input) {
using namespace bipartite_edge_coloring_internal;
assert(nl >= 0 && nr >= 0);
assert(input.size() <= std::size_t(std::numeric_limits<int>::max()));
if (input.empty()) return {};
std::vector<int> dl(nl), dr(nr);
int delta = 0;
for (auto [l, r] : input) {
assert(0 <= l && l < nl && 0 <= r && r < nr);
delta = std::max(delta, ++dl[l]);
delta = std::max(delta, ++dr[r]);
}
std::vector<int> answer(input.size());
if (delta == 1) return answer;
if (std::size_t(delta) == input.size()) {
std::iota(answer.begin(), answer.end(), 0);
return answer;
}
auto [li, nl1] = contract_vertices(dl, delta);
auto [ri, nr1] = contract_vertices(dr, delta);
int n = std::max(nl1, nr1);
std::size_t padded = std::size_t(n) * delta;
assert(padded <= 2 * input.size());
assert(padded <= std::size_t(std::numeric_limits<int>::max()));
std::vector<int> left(n), right(n);
std::vector<edge_record> es;
es.reserve(padded);
for (int id = 0; id < int(input.size()); ++id) {
int l = li[input[id].first], r = ri[input[id].second];
es.push_back({l, r, id});
++left[l];
++right[r];
}
int l = 0, r = 0;
while (l < n && r < n) {
while (l < n && left[l] == delta) ++l;
while (r < n && right[r] == delta) ++r;
if (l == n || r == n) break;
int count = std::min(delta - left[l], delta - right[r]);
for (int k = 0; k < count; ++k) es.push_back({l, r, -1});
left[l] += count;
right[r] += count;
}
assert(es.size() == padded);
std::vector<int> ids(es.size());
std::iota(ids.begin(), ids.end(), 0);
coloring_context work(n, es, answer);
work.solve(std::move(ids), delta);
return answer;
}
} // namespace noya
// NOYA_BIPARTITE_EDGE_COLORING_HPP
#ifndef NOYA_BIPARTITE_EDGE_COLORING_HPP
#define NOYA_BIPARTITE_EDGE_COLORING_HPP 1
/// @complexity Time: O(V + E sqrt(S) log(Delta + 1)); Space: O(V + E),
/// where S is the larger contracted side and S * Delta <= 2E.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_edge_coloring_internal {
inline std::pair<std::vector<int>, int>
contract_vertices(const std::vector<int> °, int delta) {
// Counting-sort positive degrees, then pack consecutive vertices. Any two
// output groups have combined degree > delta, so padding needs at most 2E
// edges. Isolated vertices need no group.
std::vector<int> end(std::size_t(delta) + 1);
for (int d : deg) if (d) ++end[d];
for (int d = 1; d <= delta; ++d) end[d] += end[d - 1];
std::vector<int> order(end.back()), map(deg.size(), -1);
for (int u = int(deg.size()); u-- > 0;)
if (deg[u]) order[--end[deg[u]]] = u;
int group = 0, sum = 0;
for (int u : order) {
if (deg[u] > delta - sum) {
++group;
sum = 0;
}
map[u] = group;
sum += deg[u];
}
return {std::move(map), order.empty() ? 0 : group + 1};
}
struct edge_record {
int l, r, id1;
};
inline std::vector<int> perfect_matching(int n,
const std::vector<edge_record> &es,
const std::vector<int> &ids) {
// Every row has the same degree, so CSR offsets are just u * degree.
const std::size_t degree = ids.size() / n;
std::vector<int> adj(ids.size()), ml(n, -1), mr(n, -1), dist(n), queue;
std::vector<std::size_t> cur(n);
for (int u = 0; u < n; ++u) cur[u] = std::size_t(u) * degree;
for (int id : ids) adj[cur[es[id].l]++] = id;
int count = 0;
for (int u = 0; u < n; ++u) {
for (std::size_t i = std::size_t(u) * degree;
i < (std::size_t(u) + 1) * degree; ++i) {
int id = adj[i], r = es[id].r;
if (mr[r] == -1) {
ml[u] = mr[r] = id;
++count;
break;
}
}
}
queue.reserve(n);
while (count < n) {
std::fill(dist.begin(), dist.end(), -1);
queue.clear();
for (int u = 0; u < n; ++u) {
if (ml[u] == -1) {
dist[u] = 0;
queue.push_back(u);
}
}
int limit = -1;
for (std::size_t head = 0; head < queue.size(); ++head) {
int u = queue[head];
if (limit >= 0 && dist[u] >= limit) continue;
for (std::size_t i = std::size_t(u) * degree;
i < (std::size_t(u) + 1) * degree; ++i) {
int id = mr[es[adj[i]].r];
if (id == -1) {
limit = dist[u] + 1;
} else {
int v = es[id].l;
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
queue.push_back(v);
}
}
}
}
assert(limit > 0); // A nonempty regular bipartite graph has a perfect match.
for (int u = 0; u < n; ++u) cur[u] = std::size_t(u) * degree;
auto dfs = [&](auto &self, int u) -> bool {
while (cur[u] < (std::size_t(u) + 1) * degree) {
int id = adj[cur[u]++], old = mr[es[id].r];
int v = old == -1 ? -1 : es[old].l;
if (v == -1 ? dist[u] + 1 == limit
: dist[v] == dist[u] + 1 && dist[v] < limit && self(self, v)) {
ml[u] = mr[es[id].r] = id;
return true;
}
}
dist[u] = -1;
return false;
};
for (int u = 0; u < n; ++u)
if (ml[u] == -1 && dfs(dfs, u)) ++count;
}
return ml;
}
struct coloring_context {
int n;
const std::vector<edge_record> &es;
std::vector<int> &answer;
std::vector<unsigned char> used;
coloring_context(int n_, const std::vector<edge_record> &es_,
std::vector<int> &answer_)
: n(n_), es(es_), answer(answer_), used(es_.size()) {}
std::vector<int> split_even_regular(std::vector<int> &ids, int degree) {
std::vector<int> adj(2 * ids.size()), other;
std::vector<std::size_t> ptr(std::size_t(n) * 2);
for (std::size_t u = 0; u < ptr.size(); ++u) ptr[u] = u * degree;
for (int id : ids) {
used[id] = 0; // Reset only this subproblem, not the entire root graph.
adj[ptr[es[id].l]++] = id;
adj[ptr[std::size_t(n) + es[id].r]++] = id;
}
for (std::size_t u = 0; u < ptr.size(); ++u) ptr[u] = u * degree;
other.reserve(ids.size() / 2);
std::size_t count = 0;
for (std::size_t s = 0; s < ptr.size(); ++s) {
// A maximal trail in an even-degree graph closes at its start. Because
// the graph is bipartite, its length is even: alternate edges directly.
std::size_t u = s;
bool parity = false;
while (true) {
while (ptr[u] < (u + 1) * degree && used[adj[ptr[u]]]) ++ptr[u];
if (ptr[u] == (u + 1) * degree) break;
int id = adj[ptr[u]++];
used[id] = 1;
if (parity) other.push_back(id);
else ids[count++] = id;
parity = !parity;
u = u < std::size_t(n) ? std::size_t(n) + es[id].r : es[id].l;
}
assert(u == s && !parity);
}
assert(count == ids.size() / 2 && other.size() == count);
ids.resize(count);
return other;
}
void assign(const std::vector<int> &ids, int color) {
for (int id : ids)
if (es[id].id1 != -1) answer[es[id].id1] = color;
}
void solve(std::vector<int> ids, int degree, int offset = 0) {
assert(degree > 0 && ids.size() == std::size_t(n) * degree);
if (degree == 1) {
assign(ids, offset);
} else if (degree % 2 == 0) {
auto other = split_even_regular(ids, degree);
solve(std::move(ids), degree / 2, offset);
solve(std::move(other), degree / 2, offset + degree / 2);
} else {
auto matching = perfect_matching(n, es, ids);
assign(matching, offset);
std::size_t count = 0;
for (int id : ids)
if (matching[es[id].l] != id) ids[count++] = id;
ids.resize(count);
solve(std::move(ids), degree - 1, offset + 1);
}
}
};
} // namespace bipartite_edge_coloring_internal
/// @brief Color a bipartite multigraph optimally using colors [0, Delta).
/// Returns colors in input-edge order; duplicate edges are distinct. The input
/// is unchanged, but the optimal coloring is not canonical. Empty input gives
/// an empty result. Original and padded edge counts must fit in int.
inline std::vector<int>
bipartite_edge_coloring(int nl, int nr,
const std::vector<std::pair<int, int>> &input) {
using namespace bipartite_edge_coloring_internal;
assert(nl >= 0 && nr >= 0);
assert(input.size() <= std::size_t(std::numeric_limits<int>::max()));
if (input.empty()) return {};
std::vector<int> dl(nl), dr(nr);
int delta = 0;
for (auto [l, r] : input) {
assert(0 <= l && l < nl && 0 <= r && r < nr);
delta = std::max(delta, ++dl[l]);
delta = std::max(delta, ++dr[r]);
}
std::vector<int> answer(input.size());
if (delta == 1) return answer;
if (std::size_t(delta) == input.size()) {
std::iota(answer.begin(), answer.end(), 0);
return answer;
}
auto [li, nl1] = contract_vertices(dl, delta);
auto [ri, nr1] = contract_vertices(dr, delta);
int n = std::max(nl1, nr1);
std::size_t padded = std::size_t(n) * delta;
assert(padded <= 2 * input.size());
assert(padded <= std::size_t(std::numeric_limits<int>::max()));
std::vector<int> left(n), right(n);
std::vector<edge_record> es;
es.reserve(padded);
for (int id = 0; id < int(input.size()); ++id) {
int l = li[input[id].first], r = ri[input[id].second];
es.push_back({l, r, id});
++left[l];
++right[r];
}
int l = 0, r = 0;
while (l < n && r < n) {
while (l < n && left[l] == delta) ++l;
while (r < n && right[r] == delta) ++r;
if (l == n || r == n) break;
int count = std::min(delta - left[l], delta - right[r]);
for (int k = 0; k < count; ++k) es.push_back({l, r, -1});
left[l] += count;
right[r] += count;
}
assert(es.size() == padded);
std::vector<int> ids(es.size());
std::iota(ids.begin(), ids.end(), 0);
coloring_context work(n, es, answer);
work.solve(std::move(ids), delta);
return answer;
}
} // namespace noya
#endif // NOYA_BIPARTITE_EDGE_COLORING_HPP
/// @complexity Time: O(V + E sqrt(S) log(Delta + 1)); Space: O(V + E),
/// where S is the larger contracted side and S * Delta <= 2E.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_edge_coloring_internal {
inline std::pair<std::vector<int>, int>
contract_vertices(const std::vector<int> °, int delta) {
// Counting-sort positive degrees, then pack consecutive vertices. Any two
// output groups have combined degree > delta, so padding needs at most 2E
// edges. Isolated vertices need no group.
std::vector<int> end(std::size_t(delta) + 1);
for (int d : deg) if (d) ++end[d];
for (int d = 1; d <= delta; ++d) end[d] += end[d - 1];
std::vector<int> order(end.back()), map(deg.size(), -1);
for (int u = int(deg.size()); u-- > 0;)
if (deg[u]) order[--end[deg[u]]] = u;
int group = 0, sum = 0;
for (int u : order) {
if (deg[u] > delta - sum) {
++group;
sum = 0;
}
map[u] = group;
sum += deg[u];
}
return {std::move(map), order.empty() ? 0 : group + 1};
}
struct edge_record {
int l, r, id1;
};
inline std::vector<int> perfect_matching(int n,
const std::vector<edge_record> &es,
const std::vector<int> &ids) {
// Every row has the same degree, so CSR offsets are just u * degree.
const std::size_t degree = ids.size() / n;
std::vector<int> adj(ids.size()), ml(n, -1), mr(n, -1), dist(n), queue;
std::vector<std::size_t> cur(n);
for (int u = 0; u < n; ++u) cur[u] = std::size_t(u) * degree;
for (int id : ids) adj[cur[es[id].l]++] = id;
int count = 0;
for (int u = 0; u < n; ++u) {
for (std::size_t i = std::size_t(u) * degree;
i < (std::size_t(u) + 1) * degree; ++i) {
int id = adj[i], r = es[id].r;
if (mr[r] == -1) {
ml[u] = mr[r] = id;
++count;
break;
}
}
}
queue.reserve(n);
while (count < n) {
std::fill(dist.begin(), dist.end(), -1);
queue.clear();
for (int u = 0; u < n; ++u) {
if (ml[u] == -1) {
dist[u] = 0;
queue.push_back(u);
}
}
int limit = -1;
for (std::size_t head = 0; head < queue.size(); ++head) {
int u = queue[head];
if (limit >= 0 && dist[u] >= limit) continue;
for (std::size_t i = std::size_t(u) * degree;
i < (std::size_t(u) + 1) * degree; ++i) {
int id = mr[es[adj[i]].r];
if (id == -1) {
limit = dist[u] + 1;
} else {
int v = es[id].l;
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
queue.push_back(v);
}
}
}
}
assert(limit > 0); // A nonempty regular bipartite graph has a perfect match.
for (int u = 0; u < n; ++u) cur[u] = std::size_t(u) * degree;
auto dfs = [&](auto &self, int u) -> bool {
while (cur[u] < (std::size_t(u) + 1) * degree) {
int id = adj[cur[u]++], old = mr[es[id].r];
int v = old == -1 ? -1 : es[old].l;
if (v == -1 ? dist[u] + 1 == limit
: dist[v] == dist[u] + 1 && dist[v] < limit && self(self, v)) {
ml[u] = mr[es[id].r] = id;
return true;
}
}
dist[u] = -1;
return false;
};
for (int u = 0; u < n; ++u)
if (ml[u] == -1 && dfs(dfs, u)) ++count;
}
return ml;
}
struct coloring_context {
int n;
const std::vector<edge_record> &es;
std::vector<int> &answer;
std::vector<unsigned char> used;
coloring_context(int n_, const std::vector<edge_record> &es_,
std::vector<int> &answer_)
: n(n_), es(es_), answer(answer_), used(es_.size()) {}
std::vector<int> split_even_regular(std::vector<int> &ids, int degree) {
std::vector<int> adj(2 * ids.size()), other;
std::vector<std::size_t> ptr(std::size_t(n) * 2);
for (std::size_t u = 0; u < ptr.size(); ++u) ptr[u] = u * degree;
for (int id : ids) {
used[id] = 0; // Reset only this subproblem, not the entire root graph.
adj[ptr[es[id].l]++] = id;
adj[ptr[std::size_t(n) + es[id].r]++] = id;
}
for (std::size_t u = 0; u < ptr.size(); ++u) ptr[u] = u * degree;
other.reserve(ids.size() / 2);
std::size_t count = 0;
for (std::size_t s = 0; s < ptr.size(); ++s) {
// A maximal trail in an even-degree graph closes at its start. Because
// the graph is bipartite, its length is even: alternate edges directly.
std::size_t u = s;
bool parity = false;
while (true) {
while (ptr[u] < (u + 1) * degree && used[adj[ptr[u]]]) ++ptr[u];
if (ptr[u] == (u + 1) * degree) break;
int id = adj[ptr[u]++];
used[id] = 1;
if (parity) other.push_back(id);
else ids[count++] = id;
parity = !parity;
u = u < std::size_t(n) ? std::size_t(n) + es[id].r : es[id].l;
}
assert(u == s && !parity);
}
assert(count == ids.size() / 2 && other.size() == count);
ids.resize(count);
return other;
}
void assign(const std::vector<int> &ids, int color) {
for (int id : ids)
if (es[id].id1 != -1) answer[es[id].id1] = color;
}
void solve(std::vector<int> ids, int degree, int offset = 0) {
assert(degree > 0 && ids.size() == std::size_t(n) * degree);
if (degree == 1) {
assign(ids, offset);
} else if (degree % 2 == 0) {
auto other = split_even_regular(ids, degree);
solve(std::move(ids), degree / 2, offset);
solve(std::move(other), degree / 2, offset + degree / 2);
} else {
auto matching = perfect_matching(n, es, ids);
assign(matching, offset);
std::size_t count = 0;
for (int id : ids)
if (matching[es[id].l] != id) ids[count++] = id;
ids.resize(count);
solve(std::move(ids), degree - 1, offset + 1);
}
}
};
} // namespace bipartite_edge_coloring_internal
/// @brief Color a bipartite multigraph optimally using colors [0, Delta).
/// Returns colors in input-edge order; duplicate edges are distinct. The input
/// is unchanged, but the optimal coloring is not canonical. Empty input gives
/// an empty result. Original and padded edge counts must fit in int.
inline std::vector<int>
bipartite_edge_coloring(int nl, int nr,
const std::vector<std::pair<int, int>> &input) {
using namespace bipartite_edge_coloring_internal;
assert(nl >= 0 && nr >= 0);
assert(input.size() <= std::size_t(std::numeric_limits<int>::max()));
if (input.empty()) return {};
std::vector<int> dl(nl), dr(nr);
int delta = 0;
for (auto [l, r] : input) {
assert(0 <= l && l < nl && 0 <= r && r < nr);
delta = std::max(delta, ++dl[l]);
delta = std::max(delta, ++dr[r]);
}
std::vector<int> answer(input.size());
if (delta == 1) return answer;
if (std::size_t(delta) == input.size()) {
std::iota(answer.begin(), answer.end(), 0);
return answer;
}
auto [li, nl1] = contract_vertices(dl, delta);
auto [ri, nr1] = contract_vertices(dr, delta);
int n = std::max(nl1, nr1);
std::size_t padded = std::size_t(n) * delta;
assert(padded <= 2 * input.size());
assert(padded <= std::size_t(std::numeric_limits<int>::max()));
std::vector<int> left(n), right(n);
std::vector<edge_record> es;
es.reserve(padded);
for (int id = 0; id < int(input.size()); ++id) {
int l = li[input[id].first], r = ri[input[id].second];
es.push_back({l, r, id});
++left[l];
++right[r];
}
int l = 0, r = 0;
while (l < n && r < n) {
while (l < n && left[l] == delta) ++l;
while (r < n && right[r] == delta) ++r;
if (l == n || r == n) break;
int count = std::min(delta - left[l], delta - right[r]);
for (int k = 0; k < count; ++k) es.push_back({l, r, -1});
left[l] += count;
right[r] += count;
}
assert(es.size() == padded);
std::vector<int> ids(es.size());
std::iota(ids.begin(), ids.end(), 0);
coloring_context work(n, es, answer);
work.solve(std::move(ids), delta);
return answer;
}
} // namespace noya
// NOYA_BIPARTITE_EDGE_COLORING_HPP