sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "graph/dm_decomposition.hpp"
Dulmage-Mendelsohn 分解 (DM分解) は,与えられた二部グラフの最大マッチングに関する性質による頂点の分類である.
この実装では,二部グラフ $G$ の頂点を3つの集合 $U, O, E$ に分類する.この分類は以下の性質を持つ:
DM 分解は疎行列のブロック対角化に用いられるらしい.行列を行と列の二部グラフとみなし,非零要素のところに辺を張って DM 分解をすると,ブロック対角化ができる (このとき,$U$を更に細かく分類することでブロックを小さくする).大規模な線形連立方程式を小さな部分問題に分解できて嬉しいらしいが,競プロで使いどころがあるかは知らない.
vector<int> dm_decomposition(int X, int Y, vector<pair<int, int>> edges)
edges
#pragma once #include <stack> #include <utility> #include <vector> #include "bipartite_matching.hpp" std::vector<int> dm_decomposition( int X, int Y, const std::vector<std::pair<int, int>>& edges) { int N = X + Y; std::vector<std::vector<int>> G(N); BipartiteMatching bm(X, Y); for (auto [u, v] : edges) { G[u].push_back(X + v); G[X + v].push_back(u); bm.add_edge(u, v); } std::vector<int> comp(N), matched(N, -1); for (auto [u, v] : bm.max_matching()) { comp[u] = comp[v] = -1; matched[u] = X + v; matched[X + v] = u; } std::stack<std::pair<int, bool>> st; // whether or not the previous edge is used in the matching for (int v = 0; v < N; ++v) { if (comp[v] == 0) { st.push({v, 0}); st.push({v, 1}); } } while (!st.empty()) { auto [u, b] = st.top(); st.pop(); for (int v : G[u]) { if (comp[v] == -1 && (b ^ (matched[u] == v))) { comp[v] = comp[u] ^ 1; st.push({v, !b}); } } } return comp; }
#line 2 "graph/dm_decomposition.hpp" #include <stack> #include <utility> #include <vector> #line 2 "graph/bipartite_matching.hpp" #include <algorithm> #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 7 "graph/dm_decomposition.hpp" std::vector<int> dm_decomposition( int X, int Y, const std::vector<std::pair<int, int>>& edges) { int N = X + Y; std::vector<std::vector<int>> G(N); BipartiteMatching bm(X, Y); for (auto [u, v] : edges) { G[u].push_back(X + v); G[X + v].push_back(u); bm.add_edge(u, v); } std::vector<int> comp(N), matched(N, -1); for (auto [u, v] : bm.max_matching()) { comp[u] = comp[v] = -1; matched[u] = X + v; matched[X + v] = u; } std::stack<std::pair<int, bool>> st; // whether or not the previous edge is used in the matching for (int v = 0; v < N; ++v) { if (comp[v] == 0) { st.push({v, 0}); st.push({v, 1}); } } while (!st.empty()) { auto [u, b] = st.top(); st.pop(); for (int v : G[u]) { if (comp[v] == -1 && (b ^ (matched[u] == v))) { comp[v] = comp[u] ^ 1; st.push({v, !b}); } } } return comp; }