This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number" #include "../../template/template.hpp" #include "../../graph/others/chromatic-number.hpp" #include "../../math/matrix/square-matrix.hpp" int main() { int N, M; cin >> N >> M; SquareMatrix< bool, 20 > g; for(int i = 0; i < M; i++) { int u, v; cin >> u >> v; g[u][v] = g[v][u] = true; } cout << chromatic_number(g) << "\n"; }
#line 1 "test/verify/yosupo-chromatic-number.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number" #line 1 "template/template.hpp" #include<bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 1e9 + 7; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { explicit FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } #line 4 "test/verify/yosupo-chromatic-number.test.cpp" #line 2 "graph/others/chromatic-number.hpp" /** * @brief Chromatic Number(彩色数) * @docs docs/chromatic-number.md * @see https://www.slideshare.net/wata_orz/ss-12131479 */ template< typename Matrix > int chromatic_number(Matrix &g) { int N = (int) g.size(); vector< int > es(N); for(int i = 0; i < (int) g.size(); i++) { for(int j = 0; j < (int) g.size(); j++) { if(g[i][j] != 0) es[i] |= 1 << j; } } vector< int > ind(1 << N); ind[0] = 1; for(int S = 1; S < (1 << N); S++) { int u = __builtin_ctz(S); ind[S] = ind[S ^ (1 << u)] + ind[(S ^ (1 << u)) & ~es[u]]; } vector< int > cnt((1 << N) + 1); for(int i = 0; i < (1 << N); i++) { cnt[ind[i]] += __builtin_parity(i) ? -1 : 1; } vector< pair< unsigned, int > > hist; for(int i = 1; i <= (1 << N); i++) { if(cnt[i]) hist.emplace_back(i, cnt[i]); } constexpr int mods[] = {1000000007, 1000000011, 1000000021}; int ret = N; for(int k = 0; k < 3; k++) { auto buf = hist; for(int c = 1; c < ret; c++) { int64_t sum = 0; for(auto&[i, x] : buf) { sum += (x = int64_t(x) * i % mods[k]); } if(sum % mods[k]) ret = c; } } return ret; } #line 1 "math/matrix/square-matrix.hpp" /** * @brief Square-Matrix(正方行列) */ template< class T, size_t N > struct SquareMatrix { array< array< T, N >, N > A; SquareMatrix() : A{{}} {} size_t size() const { return N; } inline const array< T, N > &operator[](int k) const { return (A.at(k)); } inline array< T, N > &operator[](int k) { return (A.at(k)); } static SquareMatrix add_identity() { return SquareMatrix(); } static SquareMatrix mul_identity() { SquareMatrix mat; for(size_t i = 0; i < N; i++) mat[i][i] = 1; return mat; } SquareMatrix &operator+=(const SquareMatrix &B) { for(size_t i = 0; i < N; i++) { for(size_t j = 0; j < N; j++) { (*this)[i][j] += B[i][j]; } } return *this; } SquareMatrix &operator-=(const SquareMatrix &B) { for(size_t i = 0; i < N; i++) { for(size_t j = 0; j < N; j++) { (*this)[i][j] -= B[i][j]; } } return *this; } SquareMatrix &operator*=(const SquareMatrix &B) { array< array< T, N >, N > C; for(size_t i = 0; i < N; i++) { for(size_t j = 0; j < N; j++) { for(size_t k = 0; k < N; k++) { C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]); } } } A.swap(C); return (*this); } SquareMatrix &operator^=(uint64_t k) { SquareMatrix B = SquareMatrix::mul_identity(); while(k > 0) { if(k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return *this; } SquareMatrix operator+(const SquareMatrix &B) const { return SquareMatrix(*this) += B; } SquareMatrix operator-(const SquareMatrix &B) const { return SquareMatrix(*this) -= B; } SquareMatrix operator*(const SquareMatrix &B) const { return SquareMatrix(*this) *= B; } SquareMatrix operator^(uint64_t k) const { return SquareMatrix(*this) ^= k; } friend ostream &operator<<(ostream &os, SquareMatrix &p) { for(int i = 0; i < N; i++) { os << "["; for(int j = 0; j < N; j++) { os << p[i][j] << (j + 1 == N ? "]\n" : ","); } } return os; } }; #line 7 "test/verify/yosupo-chromatic-number.test.cpp" int main() { int N, M; cin >> N >> M; SquareMatrix< bool, 20 > g; for(int i = 0; i < M; i++) { int u, v; cin >> u >> v; g[u][v] = g[v][u] = true; } cout << chromatic_number(g) << "\n"; }