verify/Chromatic_Number.test.cpp

View this file on GitHub
Last update: 2024-12-28 00:04:13+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.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);
    }

    int ans = chromatic_number(g);

    cout << ans << endl;

}

#line 1 "verify/Chromatic_Number.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 "Utility/modint.hpp"

// 動的mod : template<int mod> を消して、上の方で変数modを宣言
template <uint32_t mod> struct modint {
    using mm = modint;
    uint32_t x;
    modint() : x(0) {}
    TT modint(T a = 0) : x((ll(a) % mod + mod)) {
        if (x >= mod) x -= mod;
    }

    friend mm operator+(mm a, mm b) {
        a.x += b.x;
        if (a.x >= mod) a.x -= mod;
        return a;
    }
    friend mm operator-(mm a, mm b) {
        a.x -= b.x;
        if (a.x >= mod) a.x += mod;
        return a;
    }

    mm operator-() const { return mod - x; }

    //+と-だけで十分な場合、以下は省略して良いです。

    friend mm operator*(mm a, mm b) { return (uint64_t)(a.x) * b.x; }
    friend mm operator/(mm a, mm b) { return a * b.inv(); }
    friend mm &operator+=(mm &a, mm b) { return a = a + b; }
    friend mm &operator-=(mm &a, mm b) { return a = a - b; }
    friend mm &operator*=(mm &a, mm b) { return a = a * b; }
    friend mm &operator/=(mm &a, mm b) { return a = a * b.inv(); }

    mm inv() const {
        assert(x != 0);
        return pow(mod - 2);
    }
    mm pow(ll y) const {
        mm res = 1;
        mm v = *this;
        while (y) {
            if (y & 1) res *= v;
            v *= v;
            y /= 2;
        }
        return res;
    }

    friend istream &operator>>(istream &is, mm &a) {
        ll t;
        cin >> t;
        a = mm(t);
        return is;
    }

    friend ostream &operator<<(ostream &os, mm a) { return os << a.x; }

    bool operator==(mm a) { return x == a.x; }
    bool operator!=(mm a) { return x != a.x; }

    bool operator<(const mm &a) const { return x < a.x; }
};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1'000'000'007>;
/*
@brief modint
*/
#line 2 "Graph/Chromatic_Number.hpp"

using mint = modint998244353;
int chromatic_number(const vec<vec<int>> &g) {
    if (g.empty()) return 0;
    int n = g.size();

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

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

        ll sub = s ^ (1LL << 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;
    }

    if (dp[(1 << n) - 1] != 0) {
        return 1;
    }

    vec<mint> DP = dp;

    rep(i, 0, n) {
        rep(s, 0, 1LL << n) {
            if ((s & (1 << i)) != 0) {  // if i in s
                DP[s] += DP[s ^ (1 << i)];
            }
        }
    }

    vec<mint> DPK = DP;

    rep(k, 2, n + 1) {
        rep(i, 0, 1 << n) DPK[i] *= DP[i];
        mint v = 0;
        ll sup = (1LL << n) - 1;
        rep(s, 0, 1LL << n) {
            if (__builtin_popcountll(sup ^ s) % 2 == 0)
                v += DPK[s];
            else
                v -= DPK[s];
        }
        if (v != 0)
            return k;
        else
            continue;
    }
    return -1;
}
/*
@brief 彩色数
*/
#line 4 "verify/Chromatic_Number.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);
    }

    int ans = chromatic_number(g);

    cout << ans << endl;

}