bipartite_edge_coloring.hpp¶
用最大度种颜色给二分多重图的边染色，使相邻边颜色不同。
Complexity: Time: O(E sqrt(V) log Delta) with Euler splitting and sparse perfect matchings; Space: O(V + E).
AC 记录：bipartite_edge_coloring。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(E sqrt(V) log Delta) with Euler splitting and sparse
/// perfect matchings; Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_edge_coloring_internal {
struct dsu {
std::vector<int> fa;
explicit dsu(int siz) : fa(siz, -1) {}
int leader(int u) {
if (fa[u] < 0) {
return u;
}
return fa[u] = leader(fa[u]);
}
int merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a == b) {
return a;
}
if (fa[a] > fa[b]) {
std::swap(a, b);
}
fa[a] += fa[b];
fa[b] = a;
return a;
}
};
inline std::pair<std::vector<int>, int>
contract_vertices(const std::vector<int> °, int de1) {
const int siz = int(deg.size());
dsu ds1(siz);
std::priority_queue<std::pair<int, int>> q;
for (int u = 0; u < siz; u++) {
q.emplace(-deg[u], u);
}
while (q.size() > 1) {
auto [x, a] = q.top();
q.pop();
auto [y, b] = q.top();
q.pop();
if (-x - y > de1) {
break;
}
int rt = ds1.merge(a, b);
q.emplace(x + y, rt);
}
std::vector<int> rid(siz, -1);
std::vector<int> res(siz);
int cnt = 0;
for (int u = 0; u < siz; u++) {
int rt = ds1.leader(u);
if (rid[rt] == -1) {
rid[rt] = cnt++;
}
res[u] = rid[rt];
}
return {res, cnt};
}
struct edge_record {
int l;
int r;
int id1;
};
inline std::vector<int> perfect_matching(int siz,
const std::vector<edge_record> &es,
const std::vector<int> &eid) {
std::vector<std::vector<int>> g(siz);
for (int id : eid) {
g[es[id].l].push_back(id);
}
std::vector<int> ml(siz, -1);
std::vector<int> mr(siz, -1);
std::vector<int> dis(siz);
std::vector<int> ptr(siz);
while (true) {
std::queue<int> q;
std::fill(dis.begin(), dis.end(), -1);
std::fill(ptr.begin(), ptr.end(), 0);
for (int l = 0; l < siz; l++) {
if (ml[l] == -1) {
dis[l] = 0;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int id : g[l]) {
int nid = mr[es[id].r];
if (nid == -1) {
continue;
}
int vl = es[nid].l;
if (dis[vl] == -1) {
dis[vl] = dis[l] + 1;
q.push(vl);
}
}
}
std::function<bool(int)> aug = [&](int l) {
for (int &i = ptr[l]; i < int(g[l].size()); i++) {
int id = g[l][i];
int r = es[id].r;
int nid = mr[r];
if (nid == -1 || (dis[es[nid].l] == dis[l] + 1 && aug(es[nid].l))) {
ml[l] = id;
mr[r] = id;
return true;
}
}
dis[l] = -1;
return false;
};
int au1 = 0;
for (int l = 0; l < siz; l++) {
if (ml[l] == -1) {
au1 += aug(l);
}
}
if (au1 == 0) {
break;
}
}
for (int id : ml) {
assert(id != -1);
}
return ml;
}
inline std::pair<std::vector<int>, std::vector<int>>
split_even_regular(int siz, const std::vector<edge_record> &es,
const std::vector<int> &eid) {
std::vector<std::vector<int>> g(2 * siz);
for (int id : eid) {
g[es[id].l].push_back(id);
g[siz + es[id].r].push_back(id);
}
std::vector<int> ptr(2 * siz);
std::vector<bool> vis(es.size());
std::vector<int> a;
std::vector<int> b;
a.reserve(eid.size() / 2);
b.reserve(eid.size() / 2);
for (int s = 0; s < 2 * siz; s++) {
while (ptr[s] < int(g[s].size()) && vis[g[s][ptr[s]]]) {
ptr[s]++;
}
if (ptr[s] == int(g[s].size())) {
continue;
}
std::vector<int> vs{s};
std::vector<int> es1;
std::vector<int> cyc;
while (!vs.empty()) {
int u = vs.back();
while (ptr[u] < int(g[u].size()) && vis[g[u][ptr[u]]]) {
ptr[u]++;
}
if (ptr[u] == int(g[u].size())) {
vs.pop_back();
if (!es1.empty()) {
cyc.push_back(es1.back());
es1.pop_back();
}
continue;
}
int id = g[u][ptr[u]++];
if (vis[id]) {
continue;
}
vis[id] = true;
int nxt = u < siz ? siz + es[id].r : es[id].l;
vs.push_back(nxt);
es1.push_back(id);
}
assert(cyc.size() % 2 == 0);
for (int i = 0; i < int(cyc.size()); i++) {
(i & 1 ? b : a).push_back(cyc[i]);
}
}
assert(a.size() == eid.size() / 2);
assert(b.size() == eid.size() / 2);
return {std::move(a), std::move(b)};
}
inline void color_regular(int siz, const std::vector<edge_record> &es,
std::vector<int> eid, int deg, int off,
std::vector<int> &res) {
if (deg == 0) {
assert(eid.empty());
return;
}
assert(eid.size() == std::size_t(siz) * deg);
if (deg == 1) {
for (int id : eid) {
if (es[id].id1 != -1) {
res[es[id].id1] = off;
}
}
return;
}
if (deg % 2 == 0) {
auto [a, b] = split_even_regular(siz, es, eid);
color_regular(siz, es, std::move(a), deg / 2, off, res);
color_regular(siz, es, std::move(b), deg / 2, off + deg / 2, res);
return;
}
std::vector<int> mat = perfect_matching(siz, es, eid);
std::vector<bool> sel(es.size());
for (int id : mat) {
sel[id] = true;
if (es[id].id1 != -1) {
res[es[id].id1] = off;
}
}
std::vector<int> rem;
rem.reserve(eid.size() - siz);
for (int id : eid) {
if (!sel[id]) {
rem.push_back(id);
}
}
color_regular(siz, es, std::move(rem), deg - 1, off + 1, res);
}
} // namespace bipartite_edge_coloring_internal
/// @brief Color every edge of a bipartite multigraph with Delta colors so
/// incident edges differ. Low-degree vertices are contracted before
/// regularization, keeping the number of real and dummy edges linear.
inline std::vector<int>
bipartite_edge_coloring(int nl, int nr,
const std::vector<std::pair<int, int>> &es2) {
using namespace bipartite_edge_coloring_internal;
assert(nl >= 0 && nr >= 0);
std::vector<int> dl(nl);
std::vector<int> dr(nr);
int de1 = 0;
for (auto [l, r] : es2) {
assert(0 <= l && l < nl);
assert(0 <= r && r < nr);
de1 = std::max(de1, ++dl[l]);
de1 = std::max(de1, ++dr[r]);
}
if (es2.empty()) {
return {};
}
auto [li, nl1] = contract_vertices(dl, de1);
auto [ri, nr1] = contract_vertices(dr, de1);
int siz = std::max(nl1, nr1);
std::vector<int> cdl(siz);
std::vector<int> cdr(siz);
std::vector<edge_record> es;
es.reserve(es2.size() * 2);
for (int id = 0; id < int(es2.size()); id++) {
int l = li[es2[id].first];
int r = ri[es2[id].second];
es.push_back({l, r, id});
cdl[l]++;
cdr[r]++;
}
int l = 0;
int r = 0;
while (l < siz && r < siz) {
while (l < siz && cdl[l] == de1) {
l++;
}
while (r < siz && cdr[r] == de1) {
r++;
}
if (l == siz || r == siz) {
break;
}
int cnt = std::min(de1 - cdl[l], de1 - cdr[r]);
for (int i = 0; i < cnt; i++) {
es.push_back({l, r, -1});
}
cdl[l] += cnt;
cdr[r] += cnt;
}
assert(
std::all_of(cdl.begin(), cdl.end(), [&](int deg) { return deg == de1; }));
assert(
std::all_of(cdr.begin(), cdr.end(), [&](int deg) { return deg == de1; }));
std::vector<int> eid(es.size());
std::iota(eid.begin(), eid.end(), 0);
std::vector<int> res(es2.size(), -1);
color_regular(siz, es, std::move(eid), de1, 0, res);
for (int col : res) {
assert(0 <= col && col < de1);
}
return res;
}
} // namespace noya
#ifndef NOYA_BIPARTITE_EDGE_COLORING_HPP
#define NOYA_BIPARTITE_EDGE_COLORING_HPP 1
/// @complexity Time: O(E sqrt(V) log Delta) with Euler splitting and sparse
/// perfect matchings; Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_edge_coloring_internal {
struct dsu {
std::vector<int> fa;
explicit dsu(int siz) : fa(siz, -1) {}
int leader(int u) {
if (fa[u] < 0) {
return u;
}
return fa[u] = leader(fa[u]);
}
int merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a == b) {
return a;
}
if (fa[a] > fa[b]) {
std::swap(a, b);
}
fa[a] += fa[b];
fa[b] = a;
return a;
}
};
inline std::pair<std::vector<int>, int>
contract_vertices(const std::vector<int> °, int de1) {
const int siz = int(deg.size());
dsu ds1(siz);
std::priority_queue<std::pair<int, int>> q;
for (int u = 0; u < siz; u++) {
q.emplace(-deg[u], u);
}
while (q.size() > 1) {
auto [x, a] = q.top();
q.pop();
auto [y, b] = q.top();
q.pop();
if (-x - y > de1) {
break;
}
int rt = ds1.merge(a, b);
q.emplace(x + y, rt);
}
std::vector<int> rid(siz, -1);
std::vector<int> res(siz);
int cnt = 0;
for (int u = 0; u < siz; u++) {
int rt = ds1.leader(u);
if (rid[rt] == -1) {
rid[rt] = cnt++;
}
res[u] = rid[rt];
}
return {res, cnt};
}
struct edge_record {
int l;
int r;
int id1;
};
inline std::vector<int> perfect_matching(int siz,
const std::vector<edge_record> &es,
const std::vector<int> &eid) {
std::vector<std::vector<int>> g(siz);
for (int id : eid) {
g[es[id].l].push_back(id);
}
std::vector<int> ml(siz, -1);
std::vector<int> mr(siz, -1);
std::vector<int> dis(siz);
std::vector<int> ptr(siz);
while (true) {
std::queue<int> q;
std::fill(dis.begin(), dis.end(), -1);
std::fill(ptr.begin(), ptr.end(), 0);
for (int l = 0; l < siz; l++) {
if (ml[l] == -1) {
dis[l] = 0;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int id : g[l]) {
int nid = mr[es[id].r];
if (nid == -1) {
continue;
}
int vl = es[nid].l;
if (dis[vl] == -1) {
dis[vl] = dis[l] + 1;
q.push(vl);
}
}
}
std::function<bool(int)> aug = [&](int l) {
for (int &i = ptr[l]; i < int(g[l].size()); i++) {
int id = g[l][i];
int r = es[id].r;
int nid = mr[r];
if (nid == -1 || (dis[es[nid].l] == dis[l] + 1 && aug(es[nid].l))) {
ml[l] = id;
mr[r] = id;
return true;
}
}
dis[l] = -1;
return false;
};
int au1 = 0;
for (int l = 0; l < siz; l++) {
if (ml[l] == -1) {
au1 += aug(l);
}
}
if (au1 == 0) {
break;
}
}
for (int id : ml) {
assert(id != -1);
}
return ml;
}
inline std::pair<std::vector<int>, std::vector<int>>
split_even_regular(int siz, const std::vector<edge_record> &es,
const std::vector<int> &eid) {
std::vector<std::vector<int>> g(2 * siz);
for (int id : eid) {
g[es[id].l].push_back(id);
g[siz + es[id].r].push_back(id);
}
std::vector<int> ptr(2 * siz);
std::vector<bool> vis(es.size());
std::vector<int> a;
std::vector<int> b;
a.reserve(eid.size() / 2);
b.reserve(eid.size() / 2);
for (int s = 0; s < 2 * siz; s++) {
while (ptr[s] < int(g[s].size()) && vis[g[s][ptr[s]]]) {
ptr[s]++;
}
if (ptr[s] == int(g[s].size())) {
continue;
}
std::vector<int> vs{s};
std::vector<int> es1;
std::vector<int> cyc;
while (!vs.empty()) {
int u = vs.back();
while (ptr[u] < int(g[u].size()) && vis[g[u][ptr[u]]]) {
ptr[u]++;
}
if (ptr[u] == int(g[u].size())) {
vs.pop_back();
if (!es1.empty()) {
cyc.push_back(es1.back());
es1.pop_back();
}
continue;
}
int id = g[u][ptr[u]++];
if (vis[id]) {
continue;
}
vis[id] = true;
int nxt = u < siz ? siz + es[id].r : es[id].l;
vs.push_back(nxt);
es1.push_back(id);
}
assert(cyc.size() % 2 == 0);
for (int i = 0; i < int(cyc.size()); i++) {
(i & 1 ? b : a).push_back(cyc[i]);
}
}
assert(a.size() == eid.size() / 2);
assert(b.size() == eid.size() / 2);
return {std::move(a), std::move(b)};
}
inline void color_regular(int siz, const std::vector<edge_record> &es,
std::vector<int> eid, int deg, int off,
std::vector<int> &res) {
if (deg == 0) {
assert(eid.empty());
return;
}
assert(eid.size() == std::size_t(siz) * deg);
if (deg == 1) {
for (int id : eid) {
if (es[id].id1 != -1) {
res[es[id].id1] = off;
}
}
return;
}
if (deg % 2 == 0) {
auto [a, b] = split_even_regular(siz, es, eid);
color_regular(siz, es, std::move(a), deg / 2, off, res);
color_regular(siz, es, std::move(b), deg / 2, off + deg / 2, res);
return;
}
std::vector<int> mat = perfect_matching(siz, es, eid);
std::vector<bool> sel(es.size());
for (int id : mat) {
sel[id] = true;
if (es[id].id1 != -1) {
res[es[id].id1] = off;
}
}
std::vector<int> rem;
rem.reserve(eid.size() - siz);
for (int id : eid) {
if (!sel[id]) {
rem.push_back(id);
}
}
color_regular(siz, es, std::move(rem), deg - 1, off + 1, res);
}
} // namespace bipartite_edge_coloring_internal
/// @brief Color every edge of a bipartite multigraph with Delta colors so
/// incident edges differ. Low-degree vertices are contracted before
/// regularization, keeping the number of real and dummy edges linear.
inline std::vector<int>
bipartite_edge_coloring(int nl, int nr,
const std::vector<std::pair<int, int>> &es2) {
using namespace bipartite_edge_coloring_internal;
assert(nl >= 0 && nr >= 0);
std::vector<int> dl(nl);
std::vector<int> dr(nr);
int de1 = 0;
for (auto [l, r] : es2) {
assert(0 <= l && l < nl);
assert(0 <= r && r < nr);
de1 = std::max(de1, ++dl[l]);
de1 = std::max(de1, ++dr[r]);
}
if (es2.empty()) {
return {};
}
auto [li, nl1] = contract_vertices(dl, de1);
auto [ri, nr1] = contract_vertices(dr, de1);
int siz = std::max(nl1, nr1);
std::vector<int> cdl(siz);
std::vector<int> cdr(siz);
std::vector<edge_record> es;
es.reserve(es2.size() * 2);
for (int id = 0; id < int(es2.size()); id++) {
int l = li[es2[id].first];
int r = ri[es2[id].second];
es.push_back({l, r, id});
cdl[l]++;
cdr[r]++;
}
int l = 0;
int r = 0;
while (l < siz && r < siz) {
while (l < siz && cdl[l] == de1) {
l++;
}
while (r < siz && cdr[r] == de1) {
r++;
}
if (l == siz || r == siz) {
break;
}
int cnt = std::min(de1 - cdl[l], de1 - cdr[r]);
for (int i = 0; i < cnt; i++) {
es.push_back({l, r, -1});
}
cdl[l] += cnt;
cdr[r] += cnt;
}
assert(
std::all_of(cdl.begin(), cdl.end(), [&](int deg) { return deg == de1; }));
assert(
std::all_of(cdr.begin(), cdr.end(), [&](int deg) { return deg == de1; }));
std::vector<int> eid(es.size());
std::iota(eid.begin(), eid.end(), 0);
std::vector<int> res(es2.size(), -1);
color_regular(siz, es, std::move(eid), de1, 0, res);
for (int col : res) {
assert(0 <= col && col < de1);
}
return res;
}
} // namespace noya
#endif // NOYA_BIPARTITE_EDGE_COLORING_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(E sqrt(V) log Delta) with Euler splitting and sparse
/// perfect matchings; Space: O(V + E).
namespace noya {
namespace bipartite_edge_coloring_internal {
struct dsu {
std::vector<int> fa;
explicit dsu(int siz) : fa(siz, -1) {}
int leader(int u) {
if (fa[u] < 0) {
return u;
}
return fa[u] = leader(fa[u]);
}
int merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a == b) {
return a;
}
if (fa[a] > fa[b]) {
std::swap(a, b);
}
fa[a] += fa[b];
fa[b] = a;
return a;
}
};
inline std::pair<std::vector<int>, int>
contract_vertices(const std::vector<int> °, int de1) {
const int siz = int(deg.size());
dsu ds1(siz);
std::priority_queue<std::pair<int, int>> q;
for (int u = 0; u < siz; u++) {
q.emplace(-deg[u], u);
}
while (q.size() > 1) {
auto [x, a] = q.top();
q.pop();
auto [y, b] = q.top();
q.pop();
if (-x - y > de1) {
break;
}
int rt = ds1.merge(a, b);
q.emplace(x + y, rt);
}
std::vector<int> rid(siz, -1);
std::vector<int> res(siz);
int cnt = 0;
for (int u = 0; u < siz; u++) {
int rt = ds1.leader(u);
if (rid[rt] == -1) {
rid[rt] = cnt++;
}
res[u] = rid[rt];
}
return {res, cnt};
}
struct edge_record {
int l;
int r;
int id1;
};
inline std::vector<int> perfect_matching(int siz,
const std::vector<edge_record> &es,
const std::vector<int> &eid) {
std::vector<std::vector<int>> g(siz);
for (int id : eid) {
g[es[id].l].push_back(id);
}
std::vector<int> ml(siz, -1);
std::vector<int> mr(siz, -1);
std::vector<int> dis(siz);
std::vector<int> ptr(siz);
while (true) {
std::queue<int> q;
std::fill(dis.begin(), dis.end(), -1);
std::fill(ptr.begin(), ptr.end(), 0);
for (int l = 0; l < siz; l++) {
if (ml[l] == -1) {
dis[l] = 0;
q.push(l);
}
}
while (!q.empty()) {
int l = q.front();
q.pop();
for (int id : g[l]) {
int nid = mr[es[id].r];
if (nid == -1) {
continue;
}
int vl = es[nid].l;
if (dis[vl] == -1) {
dis[vl] = dis[l] + 1;
q.push(vl);
}
}
}
std::function<bool(int)> aug = [&](int l) {
for (int &i = ptr[l]; i < int(g[l].size()); i++) {
int id = g[l][i];
int r = es[id].r;
int nid = mr[r];
if (nid == -1 || (dis[es[nid].l] == dis[l] + 1 && aug(es[nid].l))) {
ml[l] = id;
mr[r] = id;
return true;
}
}
dis[l] = -1;
return false;
};
int au1 = 0;
for (int l = 0; l < siz; l++) {
if (ml[l] == -1) {
au1 += aug(l);
}
}
if (au1 == 0) {
break;
}
}
for (int id : ml) {
assert(id != -1);
}
return ml;
}
inline std::pair<std::vector<int>, std::vector<int>>
split_even_regular(int siz, const std::vector<edge_record> &es,
const std::vector<int> &eid) {
std::vector<std::vector<int>> g(2 * siz);
for (int id : eid) {
g[es[id].l].push_back(id);
g[siz + es[id].r].push_back(id);
}
std::vector<int> ptr(2 * siz);
std::vector<bool> vis(es.size());
std::vector<int> a;
std::vector<int> b;
a.reserve(eid.size() / 2);
b.reserve(eid.size() / 2);
for (int s = 0; s < 2 * siz; s++) {
while (ptr[s] < int(g[s].size()) && vis[g[s][ptr[s]]]) {
ptr[s]++;
}
if (ptr[s] == int(g[s].size())) {
continue;
}
std::vector<int> vs{s};
std::vector<int> es1;
std::vector<int> cyc;
while (!vs.empty()) {
int u = vs.back();
while (ptr[u] < int(g[u].size()) && vis[g[u][ptr[u]]]) {
ptr[u]++;
}
if (ptr[u] == int(g[u].size())) {
vs.pop_back();
if (!es1.empty()) {
cyc.push_back(es1.back());
es1.pop_back();
}
continue;
}
int id = g[u][ptr[u]++];
if (vis[id]) {
continue;
}
vis[id] = true;
int nxt = u < siz ? siz + es[id].r : es[id].l;
vs.push_back(nxt);
es1.push_back(id);
}
assert(cyc.size() % 2 == 0);
for (int i = 0; i < int(cyc.size()); i++) {
(i & 1 ? b : a).push_back(cyc[i]);
}
}
assert(a.size() == eid.size() / 2);
assert(b.size() == eid.size() / 2);
return {std::move(a), std::move(b)};
}
inline void color_regular(int siz, const std::vector<edge_record> &es,
std::vector<int> eid, int deg, int off,
std::vector<int> &res) {
if (deg == 0) {
assert(eid.empty());
return;
}
assert(eid.size() == std::size_t(siz) * deg);
if (deg == 1) {
for (int id : eid) {
if (es[id].id1 != -1) {
res[es[id].id1] = off;
}
}
return;
}
if (deg % 2 == 0) {
auto [a, b] = split_even_regular(siz, es, eid);
color_regular(siz, es, std::move(a), deg / 2, off, res);
color_regular(siz, es, std::move(b), deg / 2, off + deg / 2, res);
return;
}
std::vector<int> mat = perfect_matching(siz, es, eid);
std::vector<bool> sel(es.size());
for (int id : mat) {
sel[id] = true;
if (es[id].id1 != -1) {
res[es[id].id1] = off;
}
}
std::vector<int> rem;
rem.reserve(eid.size() - siz);
for (int id : eid) {
if (!sel[id]) {
rem.push_back(id);
}
}
color_regular(siz, es, std::move(rem), deg - 1, off + 1, res);
}
} // namespace bipartite_edge_coloring_internal
/// @brief Color every edge of a bipartite multigraph with Delta colors so
/// incident edges differ. Low-degree vertices are contracted before
/// regularization, keeping the number of real and dummy edges linear.
inline std::vector<int>
bipartite_edge_coloring(int nl, int nr,
const std::vector<std::pair<int, int>> &es2) {
using namespace bipartite_edge_coloring_internal;
assert(nl >= 0 && nr >= 0);
std::vector<int> dl(nl);
std::vector<int> dr(nr);
int de1 = 0;
for (auto [l, r] : es2) {
assert(0 <= l && l < nl);
assert(0 <= r && r < nr);
de1 = std::max(de1, ++dl[l]);
de1 = std::max(de1, ++dr[r]);
}
if (es2.empty()) {
return {};
}
auto [li, nl1] = contract_vertices(dl, de1);
auto [ri, nr1] = contract_vertices(dr, de1);
int siz = std::max(nl1, nr1);
std::vector<int> cdl(siz);
std::vector<int> cdr(siz);
std::vector<edge_record> es;
es.reserve(es2.size() * 2);
for (int id = 0; id < int(es2.size()); id++) {
int l = li[es2[id].first];
int r = ri[es2[id].second];
es.push_back({l, r, id});
cdl[l]++;
cdr[r]++;
}
int l = 0;
int r = 0;
while (l < siz && r < siz) {
while (l < siz && cdl[l] == de1) {
l++;
}
while (r < siz && cdr[r] == de1) {
r++;
}
if (l == siz || r == siz) {
break;
}
int cnt = std::min(de1 - cdl[l], de1 - cdr[r]);
for (int i = 0; i < cnt; i++) {
es.push_back({l, r, -1});
}
cdl[l] += cnt;
cdr[r] += cnt;
}
assert(
std::all_of(cdl.begin(), cdl.end(), [&](int deg) { return deg == de1; }));
assert(
std::all_of(cdr.begin(), cdr.end(), [&](int deg) { return deg == de1; }));
std::vector<int> eid(es.size());
std::iota(eid.begin(), eid.end(), 0);
std::vector<int> res(es2.size(), -1);
color_regular(siz, es, std::move(eid), de1, 0, res);
for (int col : res) {
assert(0 <= col && col < de1);
}
return res;
}
} // namespace noya