verify/Chromatic_Number_with_restoration.test.cpp

View this file on GitHub
Last update: 2025-01-11 07:38:14+09:00
Problem: https://judge.yosupo.jp/problem/chromatic_number

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number"
#include "../Utility/template.hpp"
#include "../Graph/Chromatic_Number_with_restoration.hpp"

int main() {
    int n, m;
    cin >> n >> m;
    vec<vec<int>> g(n);
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    auto [ans, col] = chromatic_number(g);

    vec<int> cnt(ans, 0);

    rep(i, 0, n) {
        assert(0 <= col[i]);
        assert(col[i] < ans);
        cnt[col[i]]++;
        for(int to : g[i]) {
            assert(col[i] != col[to]);
        }
    }

    rep(i, 0, ans) assert(cnt[i] != 0);

    cout << ans << endl;

}

#line 1 "verify/Chromatic_Number_with_restoration.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Algorithm/subset_transform.hpp"
template<class S, S (*op)(S, S)> vector<S> subset_zeta_transform (vector<S> f, int n) {
    rep(i, 0, n) {
        rep(s, 0, 1LL << n) {
            if((s & (1 << i)) != 0) { // if i in s
                f[s] = op(f[s], f[s ^ (1 << i)]);
            }
        }
    }
    return f;
}

template<class S, S (*op)(S, S), S (*inv)(S)> vector<S> subset_mobius_transform (vector<S> f, int n) {
    rrep(i, 0, n) {
        rep(s, 0, 1LL << n) {
            if((s & (1 << i)) != 0) { // if i in s
                f[s] = op(f[s], inv(f[s ^ (1 << i)]));
            }
        }
    }
    return f;
}
#line 2 "Convolution/bitwise_or_convolution.hpp"

// i or j = k <-> i or j が k の subset (⇔ i, jがともにkのsubset)
template<class S, S (*op)(S, S), S (*inv)(S),  S(*zero)()> vec<S> bitwise_or_convolution(vec<S> A, vec<S> B) {
    ll lg = 1;
    while(A.size() > (1LL << lg)) lg++;
    while(B.size() > (1LL << lg)) lg++;
    A.resize(1LL << lg, zero());
    B.resize(1LL << lg, zero());

    vec<S> FA = subset_zeta_transform<S, op>(A, lg);
    vec<S> FB = subset_zeta_transform<S, op>(B, lg);
    rep(i, 0, 1 << lg) FA[i] *= FB[i];
    vec<S> f = subset_mobius_transform<S, op, inv>(FA, lg);
    return f;
}
//以降の項について、0である。
#line 2 "Graph/Chromatic_Number_with_restoration.hpp"

using S = ll;
S op(S a, S b) {
    return a + b;
}
S inv(S x) {
    return -x;
}
S zero() {
    return 0;
}

pair<int, vec<int>> chromatic_number(const vec<vec<int>> &g) {
    if (g.empty()) return {0, {}};
    int n = g.size();

    vec<vec<ll>> dps(1, vec<ll>(1 << n, 0));
    dps[0][0] = 1;

    vec<ll> dp(1 << n, -1);  // dp[i][S] := S は i 色彩色可能か？
    dp[0] = 1;
    rep(i, 0, n) dp[1 << i] = 1;

    rep(s, 0, 1 << n) if (dp[s] == -1) {
        int lat = -1;
        rep(i, 0, n) if (s >> i & 1) lat = i;

        int sub = s ^ (1 << lat);
        if (dp[sub] == 0) {
            dp[s] = 0;
            continue;
        }

        bool ng = false;
        for (int to : g[lat])
            if (s >> to & 1) ng = true;

        if (ng)
            dp[s] = 0;
        else
            dp[s] = 1;
    }

    dps.push_back(dp);

    while (dps.back()[(1 << n) - 1] == 0) {
        dps.push_back(bitwise_or_convolution<S, op, inv, zero>(
            dps[1], dps[dps.size() - 1]));
        rep(i, 0, n) if (dps[dps.size() - 1][i] != 0) dps[dps.size() - 1][i] =
            1;
    }

    int K = dps.size() - 1;
    vec<int> res(n, -1);

    auto dfs = [&](auto f, int S,
                   int l) -> void {  // 集合 Sを、 [l, K)を使って彩色。
        if (S == 0) return;
        int sub = S;
        do {
            if (dps[1][sub] && dps[K - l - 1][S ^ sub]) {
                rep(i, 0, n) if (sub >> i & 1) res[i] = l;

                f(f, S ^ sub, l + 1);
                break;
            }

            sub = (sub - 1) & S;
        } while (sub != S);
    };

    dfs(dfs, (1 << n) - 1, 0);

    return {K, res};
}
#line 4 "verify/Chromatic_Number_with_restoration.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    vec<vec<int>> g(n);
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    auto [ans, col] = chromatic_number(g);

    vec<int> cnt(ans, 0);

    rep(i, 0, n) {
        assert(0 <= col[i]);
        assert(col[i] < ans);
        cnt[col[i]]++;
        for(int to : g[i]) {
            assert(col[i] != col[to]);
        }
    }

    rep(i, 0, ans) assert(cnt[i] != 0);

    cout << ans << endl;

}