test/yosupo/chromatic_number.test.cpp

View this file on GitHub
Last update: 2024-01-08 13:32:33+09:00
Problem: https://judge.yosupo.jp/problem/chromatic_number

Depends on

Chromatic Number (graph/chromatic_number.hpp)

Code

#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;
}