This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/graph/edge_coloring_of_bipartite_graph.hpp"
#ifndef SUISEN_EDGE_COLORING_OF_BIPARTITE_GRAPH #define SUISEN_EDGE_COLORING_OF_BIPARTITE_GRAPH #include <algorithm> #include <array> #include <cassert> #include <queue> #include <utility> #include <atcoder/dsu> #include "library/graph/bipartite_matching.hpp" namespace suisen { struct EdgeColoringOfBipartiteGraph { EdgeColoringOfBipartiteGraph(int l = 0, int r = 0) : l(l), r(r) {} void add_edge(int u, int v) { assert(0 <= u and u < l); assert(0 <= v and v < r); edges.emplace_back(u, v); } std::pair<int, std::vector<int>> solve() { if (edges.empty()) return {}; std::vector<int> degl(l), degr(r); for (const auto& [u, v] : edges) { ++degl[u], ++degr[v]; } const int k = std::max( *std::max_element(degl.begin(), degl.end()), *std::max_element(degr.begin(), degr.end()) ); auto [numl, idl] = contract(degl, k); auto [numr, idr] = contract(degr, k); const int n = std::max(numl, numr); degl.assign(n, 0); degr.assign(n, 0); std::vector<std::pair<int, int>> new_edges; new_edges.reserve(n * k); for (auto [u, v] : edges) { u = idl[u], v = idr[v]; new_edges.emplace_back(u, v); ++degl[u], ++degr[v]; } for (int i = 0, j = 0; i < n; ++i) { while (degl[i] < k) { while (degr[j] == k) ++j; new_edges.emplace_back(i, j); ++degl[i], ++degr[j]; } } std::vector<int> color = solve_regular(n, k, new_edges); color.resize(edges.size()); return { k, color }; } private: int l, r; std::vector<std::pair<int, int>> edges; template <typename T> using priority_queue_greater = std::priority_queue<T, std::vector<T>, std::greater<T>>; static std::vector<int> solve_regular(const int n, const int k, const std::vector<std::pair<int, int>>& edges, const int color_offset = 0) { assert(n * k == int(edges.size())); if (k == 0) { return {}; } else if (k == 1) { return std::vector<int>(edges.size(), color_offset); } else if ((k & 1) == 0) { const int m = edges.size(); const int hm = m / 2; std::vector<std::vector<std::pair<int, int>>> g(n + n); for (int i = 0; i < m; ++i) { const auto [u, v] = edges[i]; g[u].emplace_back(n + v, i); g[n + v].emplace_back(u, i); } std::vector<int> circuit; std::vector<int8_t> used(m, false), vis(n + n, false); std::vector<std::size_t> iter(n + n); for (int i = 0; i < n + n; ++i) if (not vis[i]) { auto dfs = [&](auto dfs, int u, int id) -> void { vis[u] = true; for (std::size_t &i = iter[u]; i < g[u].size(); ++i) { auto [v, nid] = g[u][i]; if (std::exchange(used[nid], true)) continue; dfs(dfs, v, nid); } if (id >= 0) circuit.push_back(id); }; dfs(dfs, i, -1); } std::array<std::vector<int>, 2> id; id[0].reserve(hm), id[1].reserve(hm); std::array<std::vector<std::pair<int, int>>, 2> nxt_edges; assert(int(circuit.size()) == m); for (int i = 0; i < m; ++i) { nxt_edges[i & 1].push_back(edges[circuit[i]]); id[i & 1].push_back(circuit[i]); } std::array<std::vector<int>, 2> rec_res; rec_res[0] = solve_regular(n, k / 2, nxt_edges[0], color_offset); rec_res[1] = solve_regular(n, k / 2, nxt_edges[1], color_offset + k / 2); std::vector<int> res(m); for (int p = 0; p < 2; ++p) { for (int i = 0; i < hm; ++i) { res[id[p][i]] = rec_res[p][i]; } } return res; } else { BipartiteMatching bimatch(n, n); for (const auto& [u, v] : edges) bimatch.add_edge(u, v); const int matching_size = bimatch.solve(); assert(matching_size == n); std::vector<std::pair<int, int>> nxt_edges; const int m = edges.size(); std::vector<int> res(m); std::vector<int> id(m - n); std::vector<int8_t> used(n, false); for (int i = 0; i < m; ++i) { auto [u, v] = edges[i]; if (bimatch.right(u) == v and not std::exchange(used[u], true)) { res[i] = color_offset; } else { id[nxt_edges.size()] = i; nxt_edges.emplace_back(u, v); } } std::vector<int> rec_res = solve_regular(n, k - 1, nxt_edges, color_offset + 1); assert(rec_res.size() == nxt_edges.size()); for (int i = 0; i < m - n; ++i) res[id[i]] = rec_res[i]; return res; } } static std::pair<int, std::vector<int>> contract(const std::vector<int>& deg, const int k) { const int n = deg.size(); atcoder::dsu uf(n); priority_queue_greater<std::pair<int, int>> pq{}; for (int i = 0; i < n; ++i) pq.emplace(deg[i], i); while (pq.size() >= 2) { auto [di, i] = pq.top(); pq.pop(); auto [dj, j] = pq.top(); pq.pop(); if (di + dj <= k) { uf.merge(i, j); pq.emplace(di + dj, uf.leader(i)); } else break; } auto groups = uf.groups(); const int m = groups.size(); std::vector<int> cmp_id(n); for (int i = 0; i < m; ++i) for (int v : groups[i]) { cmp_id[v] = i; } return { m, cmp_id }; } }; } // namespace suisen #endif // SUISEN_EDGE_COLORING_OF_BIPARTITE_GRAPH
#line 1 "library/graph/edge_coloring_of_bipartite_graph.hpp" #include <algorithm> #include <array> #include <cassert> #include <queue> #include <utility> #include <atcoder/dsu> #line 1 "library/graph/bipartite_matching.hpp" #line 6 "library/graph/bipartite_matching.hpp" #include <deque> #include <random> #line 9 "library/graph/bipartite_matching.hpp" #include <vector> namespace suisen { struct BipartiteMatching { static constexpr int ABSENT = -1; BipartiteMatching() = default; BipartiteMatching(int n, int m) : _n(n), _m(m), _to_r(_n, ABSENT), _to_l(_m, ABSENT), _g(n + m) {} void add_edge(int fr, int to) { _g[fr].push_back(to), _f = -1; } // template <bool shuffle = true> // int solve_heuristics() { // if (_f >= 0) return _f; // static std::mt19937 rng(std::random_device{}()); // if constexpr (shuffle) for (auto& adj : _g) std::shuffle(adj.begin(), adj.end(), rng); // std::vector<int8_t> vis(_n, false); // auto dfs = [&, this](auto dfs, int u) -> bool { // if (std::exchange(vis[u], true)) return false; // for (int v : _g[u]) if (_to_l[v] == ABSENT) return _to_r[u] = v, _to_l[v] = u, true; // for (int v : _g[u]) if (dfs(dfs, _to_l[v])) return _to_r[u] = v, _to_l[v] = u, true; // return false; // }; // for (bool upd = true; std::exchange(upd, false);) { // vis.assign(_n, false); // for (int i = 0; i < _n; ++i) if (_to_r[i] == ABSENT) upd |= dfs(dfs, i); // } // return _f = _n - std::count(_to_r.begin(), _to_r.end(), ABSENT); // } int solve() { if (_f >= 0) return _f; const auto h = reversed_graph(); std::vector<int> level(_n + _m), iter(_n + _m); std::deque<int> que; auto bfs = [&] { for (int i = 0; i < _n; ++i) { if (_to_r[i] == ABSENT) level[i] = 0, que.push_back(i); else level[i] = -1; } std::fill(level.begin() + _n, level.end(), -1); bool ok = false; while (not que.empty()) { const int l = que.front(); que.pop_front(); for (int r : _g[l]) if (_to_r[l] != r and level[_n + r] < 0) { const int nl = _to_l[r]; level[_n + r] = level[l] + 1; if (nl == ABSENT) ok = true; else if (level[nl] < 0) level[nl] = level[l] + 2, que.push_back(nl); } } return ok; }; auto dfs = [&](auto dfs, const int r) -> bool { const int level_v = level[_n + r]; if (level_v < 0) return false; const int dr = h[r].size(); for (int &i = iter[_n + r]; i < dr; ++i) { const int l = h[r][i]; if (level_v <= level[l] or _to_l[r] == l or iter[l] > _m) continue; if (int nr = _to_r[l]; nr == ABSENT) { iter[l] = _m + 1, level[l] = _n + _m; _to_r[l] = r, _to_l[r] = l; return true; } else if (iter[l] <= nr) { iter[l] = nr + 1; if (level[l] > level[_n + nr] and dfs(dfs, nr)) { _to_r[l] = r, _to_l[r] = l; return true; } iter[l] = _m + 1, level[l] = _n + _m; } } return level[_n + r] = _n + _m, false; }; for (_f = 0; bfs();) { std::fill(iter.begin(), iter.end(), 0); for (int j = 0; j < _m; ++j) if (_to_l[j] == ABSENT) _f += dfs(dfs, j); } return _f; } std::vector<std::pair<int, int>> max_matching() { if (_f < 0) solve(); std::vector<std::pair<int, int>> res; res.reserve(_f); for (int i = 0; i < _n; ++i) if (_to_r[i] != ABSENT) res.emplace_back(i, _to_r[i]); return res; } std::vector<std::pair<int, int>> min_edge_cover() { auto res = max_matching(); std::vector<bool> vl(_n, false), vr(_n, false); for (const auto& [u, v] : res) vl[u] = vr[v] = true; for (int u = 0; u < _n; ++u) for (int v : _g[u]) if (not (vl[u] and vr[v])) { vl[u] = vr[v] = true; res.emplace_back(u, v); } return res; } std::vector<int> min_vertex_cover() { if (_f < 0) solve(); std::vector<std::vector<int>> g(_n + _m); std::vector<bool> cl(_n, true), cr(_m, false); for (int u = 0; u < _n; ++u) for (int v : _g[u]) { if (_to_r[u] == v) { g[v + _n].push_back(u); cl[u] = false; } else { g[u].push_back(v + _n); } } std::vector<bool> vis(_n + _m, false); std::deque<int> dq; for (int i = 0; i < _n; ++i) if (cl[i]) { dq.push_back(i); vis[i] = true; } while (dq.size()) { int u = dq.front(); dq.pop_front(); for (int v : g[u]) { if (vis[v]) continue; vis[v] = true; (v < _n ? cl[v] : cr[v - _n]) = true; dq.push_back(v); } } std::vector<int> res; for (int i = 0; i < _n; ++i) if (not cl[i]) res.push_back(i); for (int i = 0; i < _m; ++i) if (cr[i]) res.push_back(_n + i); return res; } std::vector<int> max_independent_set() { std::vector<bool> use(_n + _m, true); for (int v : min_vertex_cover()) use[v] = false; std::vector<int> res; for (int i = 0; i < _n + _m; ++i) if (use[i]) res.push_back(i); return res; } int left_size() const { return _n; } int right_size() const { return _m; } std::pair<int, int> size() const { return { _n, _m }; } int right(int l) const { assert(_f >= 0); return _to_r[l]; } int left(int r) const { assert(_f >= 0); return _to_l[r]; } const auto graph() const { return _g; } std::vector<std::vector<int>> reversed_graph() const { std::vector<std::vector<int>> h(_m); for (int i = 0; i < _n; ++i) for (int j : _g[i]) h[j].push_back(i); return h; } private: int _n, _m; std::vector<int> _to_r, _to_l; std::vector<std::vector<int>> _g; int _f = 0; }; } // namespace suisen #line 13 "library/graph/edge_coloring_of_bipartite_graph.hpp" namespace suisen { struct EdgeColoringOfBipartiteGraph { EdgeColoringOfBipartiteGraph(int l = 0, int r = 0) : l(l), r(r) {} void add_edge(int u, int v) { assert(0 <= u and u < l); assert(0 <= v and v < r); edges.emplace_back(u, v); } std::pair<int, std::vector<int>> solve() { if (edges.empty()) return {}; std::vector<int> degl(l), degr(r); for (const auto& [u, v] : edges) { ++degl[u], ++degr[v]; } const int k = std::max( *std::max_element(degl.begin(), degl.end()), *std::max_element(degr.begin(), degr.end()) ); auto [numl, idl] = contract(degl, k); auto [numr, idr] = contract(degr, k); const int n = std::max(numl, numr); degl.assign(n, 0); degr.assign(n, 0); std::vector<std::pair<int, int>> new_edges; new_edges.reserve(n * k); for (auto [u, v] : edges) { u = idl[u], v = idr[v]; new_edges.emplace_back(u, v); ++degl[u], ++degr[v]; } for (int i = 0, j = 0; i < n; ++i) { while (degl[i] < k) { while (degr[j] == k) ++j; new_edges.emplace_back(i, j); ++degl[i], ++degr[j]; } } std::vector<int> color = solve_regular(n, k, new_edges); color.resize(edges.size()); return { k, color }; } private: int l, r; std::vector<std::pair<int, int>> edges; template <typename T> using priority_queue_greater = std::priority_queue<T, std::vector<T>, std::greater<T>>; static std::vector<int> solve_regular(const int n, const int k, const std::vector<std::pair<int, int>>& edges, const int color_offset = 0) { assert(n * k == int(edges.size())); if (k == 0) { return {}; } else if (k == 1) { return std::vector<int>(edges.size(), color_offset); } else if ((k & 1) == 0) { const int m = edges.size(); const int hm = m / 2; std::vector<std::vector<std::pair<int, int>>> g(n + n); for (int i = 0; i < m; ++i) { const auto [u, v] = edges[i]; g[u].emplace_back(n + v, i); g[n + v].emplace_back(u, i); } std::vector<int> circuit; std::vector<int8_t> used(m, false), vis(n + n, false); std::vector<std::size_t> iter(n + n); for (int i = 0; i < n + n; ++i) if (not vis[i]) { auto dfs = [&](auto dfs, int u, int id) -> void { vis[u] = true; for (std::size_t &i = iter[u]; i < g[u].size(); ++i) { auto [v, nid] = g[u][i]; if (std::exchange(used[nid], true)) continue; dfs(dfs, v, nid); } if (id >= 0) circuit.push_back(id); }; dfs(dfs, i, -1); } std::array<std::vector<int>, 2> id; id[0].reserve(hm), id[1].reserve(hm); std::array<std::vector<std::pair<int, int>>, 2> nxt_edges; assert(int(circuit.size()) == m); for (int i = 0; i < m; ++i) { nxt_edges[i & 1].push_back(edges[circuit[i]]); id[i & 1].push_back(circuit[i]); } std::array<std::vector<int>, 2> rec_res; rec_res[0] = solve_regular(n, k / 2, nxt_edges[0], color_offset); rec_res[1] = solve_regular(n, k / 2, nxt_edges[1], color_offset + k / 2); std::vector<int> res(m); for (int p = 0; p < 2; ++p) { for (int i = 0; i < hm; ++i) { res[id[p][i]] = rec_res[p][i]; } } return res; } else { BipartiteMatching bimatch(n, n); for (const auto& [u, v] : edges) bimatch.add_edge(u, v); const int matching_size = bimatch.solve(); assert(matching_size == n); std::vector<std::pair<int, int>> nxt_edges; const int m = edges.size(); std::vector<int> res(m); std::vector<int> id(m - n); std::vector<int8_t> used(n, false); for (int i = 0; i < m; ++i) { auto [u, v] = edges[i]; if (bimatch.right(u) == v and not std::exchange(used[u], true)) { res[i] = color_offset; } else { id[nxt_edges.size()] = i; nxt_edges.emplace_back(u, v); } } std::vector<int> rec_res = solve_regular(n, k - 1, nxt_edges, color_offset + 1); assert(rec_res.size() == nxt_edges.size()); for (int i = 0; i < m - n; ++i) res[id[i]] = rec_res[i]; return res; } } static std::pair<int, std::vector<int>> contract(const std::vector<int>& deg, const int k) { const int n = deg.size(); atcoder::dsu uf(n); priority_queue_greater<std::pair<int, int>> pq{}; for (int i = 0; i < n; ++i) pq.emplace(deg[i], i); while (pq.size() >= 2) { auto [di, i] = pq.top(); pq.pop(); auto [dj, j] = pq.top(); pq.pop(); if (di + dj <= k) { uf.merge(i, j); pq.emplace(di + dj, uf.leader(i)); } else break; } auto groups = uf.groups(); const int m = groups.size(); std::vector<int> cmp_id(n); for (int i = 0; i < m; ++i) for (int v : groups[i]) { cmp_id[v] = i; } return { m, cmp_id }; } }; } // namespace suisen