sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "graph/bipartite_edge_coloring.hpp"
二部グラフの辺彩色を求める.
Kőnig’s Line Coloring Theorem によると,二部グラフ $G$ の頂点の最大次数を $D$ とすると,$G$ は必ず $D$ 色で辺彩色可能である.
vector<int> bipartite_edge_coloring(vector<pair<int, int>> G, int n, int m)
計算量解析あってるかわからん.
正則二部グラフの完全マッチングを $O(E\log V)$ 時間で求めるアルゴリズムを用いれば,時間計算量を $O(E\log E)$ に改善できる.ただし,実測では普通に Hopcroft-Karp をやったほうが速かった.アルゴリズムについては,参考文献 (Twitter) を参照.
#pragma once #include <algorithm> #include <bit> #include <map> #include <stack> #include <utility> #include <vector> #include "../graph/bipartite_matching.hpp" std::vector<int> bipartite_edge_coloring( const std::vector<std::pair<int, int>>& edges, int n1, int n2) { const int E = edges.size(); // find the maximum degree D std::vector<int> deg1(n1), deg2(n2); for (auto [a, b] : edges) { ++deg1[a], ++deg2[b]; } const int D = std::max(*std::ranges::max_element(deg1), *std::ranges::max_element(deg2)); // convert to D-regular bipartite graph // merge vertices with the sum of degrees <= D auto contract = [&](const auto& deg) { const int n = deg.size(); std::vector<std::pair<int, int>> vs(n); for (int i = 0; i < n; ++i) vs[i] = {deg[i], i}; std::ranges::sort(vs); std::vector<int> id(n); std::vector<int> ndeg; int k = 0; for (int i = 0; i < n;) { int d = 0; int j = i; while (j < n && d + vs[j].first <= D) { d += vs[j].first; id[vs[j].second] = k; ++j; } ndeg.push_back(d); ++k; i = j; } return std::make_pair(id, ndeg); }; auto [id1, ndeg1] = contract(deg1); auto [id2, ndeg2] = contract(deg2); using Edge = std::tuple<int, int, int>; std::vector<Edge> edges2; for (int i = 0; i < E; ++i) { auto [a, b] = edges[i]; edges2.emplace_back(id1[a], id2[b], i); } // add dummy vertices const int n = std::max(ndeg1.size(), ndeg2.size()); ndeg1.resize(n); ndeg2.resize(n); // add dummy edges int j = 0; int nE = E; for (int i = 0; i < n; ++i) { while (ndeg1[i] < D) { while (ndeg2[j] == D) ++j; edges2.emplace_back(i, j, nE++); ++ndeg1[i]; ++ndeg2[j]; } } // find the edge coloring std::vector<int> color(nE); int k = 0; auto rec = [&](auto& rec, const std::vector<Edge>& edges, int D) -> void { if (D == 1) { for (auto [a, b, i] : edges) { color[i] = k; } ++k; return; } else if (D % 2 == 0) { // find an eulerian walk for each connected component // partition the graph into two std::vector<std::vector<std::pair<int, int>>> G(2 * n); for (int j = 0; j < (int)edges.size(); ++j) { auto [a, b, i] = edges[j]; G[a].emplace_back(n + b, j); G[n + b].emplace_back(a, j); } std::vector<bool> used_v(2 * n), used_e(edges.size()); std::vector<std::vector<Edge>> edges2(2); for (int v = 0; v < n; ++v) { if (used_v[v]) continue; std::vector<int> walk; std::stack<std::pair<int, int>> st; st.emplace(v, -1); while (!st.empty()) { auto [u, j] = st.top(); used_v[u] = true; while (!G[u].empty() && used_e[G[u].back().second]) { G[u].pop_back(); } if (G[u].empty()) { walk.push_back(j); st.pop(); } else { auto [v, k] = G[u].back(); G[u].pop_back(); used_e[k] = true; st.emplace(v, k); } } for (int i = 0; i < (int)walk.size() - 1; ++i) { edges2[i % 2].push_back(edges[walk[i]]); } } rec(rec, edges2[0], D / 2); int nD = std::bit_ceil((unsigned int)(D / 2)); // add nD-D/2 edges from edges2[0] to edges2[1] for (auto [a, b, i] : edges2[0]) { if (color[i] >= k - (nD - D / 2)) { edges2[1].emplace_back(a, b, i); } } k -= nD - D / 2; rec(rec, edges2[1], nD); } else { // paint the edges in a perfect matching with the same color BipartiteMatching bm(n, n); for (auto [a, b, i] : edges) { bm.add_edge(a, b); } std::vector<int> match(n, -1); for (auto [a, b] : bm.max_matching()) { match[a] = b; } std::vector<Edge> edges2; for (auto [a, b, i] : edges) { if (match[a] == b) { color[i] = k; match[a] = -1; } else { edges2.emplace_back(a, b, i); } } ++k; rec(rec, edges2, D - 1); } }; rec(rec, edges2, D); color.resize(E); return color; } std::vector<std::pair<int, int>> regular_bipartite_matching( const std::vector<std::pair<int, int>>& edges, int D) { const int n = edges.size() / D; auto rec = [&](auto& rec, const auto& edges, int D) { if (D == 1) { return edges; } else if (D % 2 == 0) { // find an eulerian walk for each connected component // partition the graph into two std::vector<std::vector<std::pair<int, int>>> G(2 * n); for (int j = 0; j < (int)edges.size(); ++j) { auto [a, b, d] = edges[j]; G[a].emplace_back(n + b, j); G[n + b].emplace_back(a, j); } std::vector<bool> used_v(2 * n), used_e(edges.size()); std::vector<std::vector<std::tuple<int, int, bool>>> edges2(2); std::vector<int> dummy_cnt(2); for (int v = 0; v < n; ++v) { if (used_v[v]) continue; std::vector<int> walk; std::stack<std::pair<int, int>> st; st.emplace(v, -1); while (!st.empty()) { auto [u, j] = st.top(); used_v[u] = true; while (!G[u].empty() && used_e[G[u].back().second]) { G[u].pop_back(); } if (G[u].empty()) { walk.push_back(j); st.pop(); } else { auto [v, k] = G[u].back(); G[u].pop_back(); used_e[k] = true; st.emplace(v, k); } } for (int i = 0; i < (int)walk.size() - 1; ++i) { edges2[i % 2].push_back(edges[walk[i]]); dummy_cnt[i % 2] += std::get<2>(edges[walk[i]]); } } return rec(rec, dummy_cnt[0] < dummy_cnt[1] ? edges2[0] : edges2[1], D / 2); } else { int size = std::bit_ceil((unsigned int)D); // add size-D dummy edges auto edges2 = edges; for (int i = 0; i < n; ++i) { for (int j = 0; j < size - D; ++j) { edges2.emplace_back(i, i, true); } } while (true) { auto res = rec(rec, edges2, size); int cnt = 0; for (auto [a, b, d] : res) { cnt += d; } if (cnt == 0) return res; // add res size-D times edges2 = edges; for (auto [a, b, d] : res) { for (int j = 0; j < size - D; ++j) { edges2.emplace_back(a, b, d); } } } } }; std::vector<std::tuple<int, int, bool>> edges2; for (auto [a, b] : edges) { edges2.emplace_back(a, b, false); } auto res = rec(rec, edges2, D); std::vector<std::pair<int, int>> ret; for (auto [a, b, d] : res) { ret.emplace_back(a, b); } return ret; }
#line 2 "graph/bipartite_edge_coloring.hpp" #include <algorithm> #include <bit> #include <map> #include <stack> #include <utility> #include <vector> #line 3 "graph/bipartite_matching.hpp" #include <limits> #include <queue> #line 7 "graph/bipartite_matching.hpp" class BipartiteMatching { public: BipartiteMatching() = default; BipartiteMatching(int U, int V) : U(U), V(V), NIL(U + V), G(U), level(U + V + 1), match(U + V + 1, NIL) {} void add_edge(int u, int v) { G[u].emplace_back(U + v); } std::vector<std::pair<int, int>> max_matching() { while (bfs()) { for (int u = 0; u < U; ++u) { if (match[u] == NIL) { dfs(u); } } } std::vector<std::pair<int, int>> ret; for (int u = 0; u < U; ++u) { if (match[u] != NIL) ret.emplace_back(u, match[u] - U); } return ret; } private: static constexpr int INF = std::numeric_limits<int>::max() / 2; const int U, V, NIL; std::vector<std::vector<int>> G; std::vector<int> level, match; bool bfs() { std::ranges::fill(level, INF); std::queue<int> q; for (int u = 0; u < U; ++u) { if (match[u] == NIL) { level[u] = 0; q.push(u); } } while (!q.empty()) { int u = q.front(); q.pop(); if (level[u] < level[NIL]) { for (int v : G[u]) { if (level[match[v]] == INF) { level[match[v]] = level[u] + 1; q.push(match[v]); } } } } return level[NIL] != INF; } bool dfs(int u) { if (u == NIL) return true; for (int v : G[u]) { if (level[match[v]] == level[u] + 1 && dfs(match[v])) { match[v] = u; match[u] = v; return true; } } level[u] = INF; return false; } }; /* * Bipartite matching using Ford-Fulkerson algorithm * Time complexity: O(VE) */ class BipartiteMatchingFF { public: BipartiteMatchingFF() = default; explicit BipartiteMatchingFF(int n) : G(n), used(n), match(n) {} void add_edge(int u, int v) { G[u].push_back(v); G[v].push_back(u); } std::vector<std::pair<int, int>> max_matching() { int res = 0; std::ranges::fill(match, -1); for (int v = 0; v < (int)G.size(); ++v) { if (match[v] == -1) { std::fill(used.begin(), used.end(), false); if (dfs(v)) ++res; } } std::vector<std::pair<int, int>> ret; for (int i = 0; i < (int)G.size(); ++i) { if (i < match[i]) ret.emplace_back(i, match[i]); } return ret; } private: std::vector<std::vector<int>> G; std::vector<bool> used; std::vector<int> match; bool dfs(int u) { used[u] = true; for (int v : G[u]) { int w = match[v]; if (w == -1 || (!used[w] && dfs(w))) { match[u] = v; match[v] = u; return true; } } return false; } }; #line 10 "graph/bipartite_edge_coloring.hpp" std::vector<int> bipartite_edge_coloring( const std::vector<std::pair<int, int>>& edges, int n1, int n2) { const int E = edges.size(); // find the maximum degree D std::vector<int> deg1(n1), deg2(n2); for (auto [a, b] : edges) { ++deg1[a], ++deg2[b]; } const int D = std::max(*std::ranges::max_element(deg1), *std::ranges::max_element(deg2)); // convert to D-regular bipartite graph // merge vertices with the sum of degrees <= D auto contract = [&](const auto& deg) { const int n = deg.size(); std::vector<std::pair<int, int>> vs(n); for (int i = 0; i < n; ++i) vs[i] = {deg[i], i}; std::ranges::sort(vs); std::vector<int> id(n); std::vector<int> ndeg; int k = 0; for (int i = 0; i < n;) { int d = 0; int j = i; while (j < n && d + vs[j].first <= D) { d += vs[j].first; id[vs[j].second] = k; ++j; } ndeg.push_back(d); ++k; i = j; } return std::make_pair(id, ndeg); }; auto [id1, ndeg1] = contract(deg1); auto [id2, ndeg2] = contract(deg2); using Edge = std::tuple<int, int, int>; std::vector<Edge> edges2; for (int i = 0; i < E; ++i) { auto [a, b] = edges[i]; edges2.emplace_back(id1[a], id2[b], i); } // add dummy vertices const int n = std::max(ndeg1.size(), ndeg2.size()); ndeg1.resize(n); ndeg2.resize(n); // add dummy edges int j = 0; int nE = E; for (int i = 0; i < n; ++i) { while (ndeg1[i] < D) { while (ndeg2[j] == D) ++j; edges2.emplace_back(i, j, nE++); ++ndeg1[i]; ++ndeg2[j]; } } // find the edge coloring std::vector<int> color(nE); int k = 0; auto rec = [&](auto& rec, const std::vector<Edge>& edges, int D) -> void { if (D == 1) { for (auto [a, b, i] : edges) { color[i] = k; } ++k; return; } else if (D % 2 == 0) { // find an eulerian walk for each connected component // partition the graph into two std::vector<std::vector<std::pair<int, int>>> G(2 * n); for (int j = 0; j < (int)edges.size(); ++j) { auto [a, b, i] = edges[j]; G[a].emplace_back(n + b, j); G[n + b].emplace_back(a, j); } std::vector<bool> used_v(2 * n), used_e(edges.size()); std::vector<std::vector<Edge>> edges2(2); for (int v = 0; v < n; ++v) { if (used_v[v]) continue; std::vector<int> walk; std::stack<std::pair<int, int>> st; st.emplace(v, -1); while (!st.empty()) { auto [u, j] = st.top(); used_v[u] = true; while (!G[u].empty() && used_e[G[u].back().second]) { G[u].pop_back(); } if (G[u].empty()) { walk.push_back(j); st.pop(); } else { auto [v, k] = G[u].back(); G[u].pop_back(); used_e[k] = true; st.emplace(v, k); } } for (int i = 0; i < (int)walk.size() - 1; ++i) { edges2[i % 2].push_back(edges[walk[i]]); } } rec(rec, edges2[0], D / 2); int nD = std::bit_ceil((unsigned int)(D / 2)); // add nD-D/2 edges from edges2[0] to edges2[1] for (auto [a, b, i] : edges2[0]) { if (color[i] >= k - (nD - D / 2)) { edges2[1].emplace_back(a, b, i); } } k -= nD - D / 2; rec(rec, edges2[1], nD); } else { // paint the edges in a perfect matching with the same color BipartiteMatching bm(n, n); for (auto [a, b, i] : edges) { bm.add_edge(a, b); } std::vector<int> match(n, -1); for (auto [a, b] : bm.max_matching()) { match[a] = b; } std::vector<Edge> edges2; for (auto [a, b, i] : edges) { if (match[a] == b) { color[i] = k; match[a] = -1; } else { edges2.emplace_back(a, b, i); } } ++k; rec(rec, edges2, D - 1); } }; rec(rec, edges2, D); color.resize(E); return color; } std::vector<std::pair<int, int>> regular_bipartite_matching( const std::vector<std::pair<int, int>>& edges, int D) { const int n = edges.size() / D; auto rec = [&](auto& rec, const auto& edges, int D) { if (D == 1) { return edges; } else if (D % 2 == 0) { // find an eulerian walk for each connected component // partition the graph into two std::vector<std::vector<std::pair<int, int>>> G(2 * n); for (int j = 0; j < (int)edges.size(); ++j) { auto [a, b, d] = edges[j]; G[a].emplace_back(n + b, j); G[n + b].emplace_back(a, j); } std::vector<bool> used_v(2 * n), used_e(edges.size()); std::vector<std::vector<std::tuple<int, int, bool>>> edges2(2); std::vector<int> dummy_cnt(2); for (int v = 0; v < n; ++v) { if (used_v[v]) continue; std::vector<int> walk; std::stack<std::pair<int, int>> st; st.emplace(v, -1); while (!st.empty()) { auto [u, j] = st.top(); used_v[u] = true; while (!G[u].empty() && used_e[G[u].back().second]) { G[u].pop_back(); } if (G[u].empty()) { walk.push_back(j); st.pop(); } else { auto [v, k] = G[u].back(); G[u].pop_back(); used_e[k] = true; st.emplace(v, k); } } for (int i = 0; i < (int)walk.size() - 1; ++i) { edges2[i % 2].push_back(edges[walk[i]]); dummy_cnt[i % 2] += std::get<2>(edges[walk[i]]); } } return rec(rec, dummy_cnt[0] < dummy_cnt[1] ? edges2[0] : edges2[1], D / 2); } else { int size = std::bit_ceil((unsigned int)D); // add size-D dummy edges auto edges2 = edges; for (int i = 0; i < n; ++i) { for (int j = 0; j < size - D; ++j) { edges2.emplace_back(i, i, true); } } while (true) { auto res = rec(rec, edges2, size); int cnt = 0; for (auto [a, b, d] : res) { cnt += d; } if (cnt == 0) return res; // add res size-D times edges2 = edges; for (auto [a, b, d] : res) { for (int j = 0; j < size - D; ++j) { edges2.emplace_back(a, b, d); } } } } }; std::vector<std::tuple<int, int, bool>> edges2; for (auto [a, b] : edges) { edges2.emplace_back(a, b, false); } auto res = rec(rec, edges2, D); std::vector<std::pair<int, int>> ret; for (auto [a, b, d] : res) { ret.emplace_back(a, b); } return ret; }