sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number" #include "../../graph/chromatic_number.hpp" #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<bool>> G(N, vector<bool>(N)); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; G[u][v] = G[v][u] = true; } cout << chromatic_number(G) << endl; }
#line 1 "test/yosupo/chromatic_number.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number" #line 2 "graph/chromatic_number.hpp" #include <bit> #include <vector> int chromatic_number(std::vector<std::vector<bool>>& G) { const int n = G.size(); std::vector<int> neighbor(n); for (int i = 0; i < (int)G.size(); ++i) { for (int j = 0; j < (int)G.size(); ++j) { if (G[i][j]) neighbor[i] |= 1 << j; } } // number of subsets of S that are independent std::vector<int> ind(1 << n); ind[0] = 1; for (int S = 1; S < (1 << n); ++S) { int v = std::countr_zero((unsigned int)S); // (not containing v) + (containing v) ind[S] = ind[S ^ (1 << v)] + ind[(S ^ (1 << v)) & ~neighbor[v]]; } // number of ways to choose k subsets of S that are independent auto f = ind; for (int k = 1;; ++k) { // numer of ways to choose k subsets of S so that they cover S int g = 0; for (int S = 0; S < (1 << n); ++S) { g += (std::popcount((unsigned int)S) & 1 ? -1 : 1) * f[S]; } if (g) return k; for (int S = 1; S < (1 << n); ++S) { f[S] *= ind[S]; } } } #line 4 "test/yosupo/chromatic_number.test.cpp" #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<bool>> G(N, vector<bool>(N)); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; G[u][v] = G[v][u] = true; } cout << chromatic_number(G) << endl; }