test/yosupo-judge/chromatic_number/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://judge.yosupo.jp/problem/chromatic_number
• Link: View error logs on GitHub Actions

Depends on

• Graph vertex coloring (Mylib/Graph/Coloring/chromatic_number.cpp)
• Mod pow (Mylib/Number/Mod/mod_pow.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number"

#include <iostream>
#include <vector>
#include "Mylib/Graph/Coloring/chromatic_number.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, M;
  std::cin >> N >> M;
  std::vector<std::vector<int>> g(N);

  for (int i = 0; i < M; ++i) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  int ans = hl::chromatic_number(g);
  std::cout << ans << "\n";

  return 0;
}

#line 1 "test/yosupo-judge/chromatic_number/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number"

#include <iostream>
#include <vector>
#line 2 "Mylib/Graph/Coloring/chromatic_number.cpp"
#include <cmath>
#include <cstdint>
#line 3 "Mylib/Number/Mod/mod_pow.cpp"

namespace haar_lib {
  constexpr int64_t mod_pow(int64_t n, int64_t p, int64_t m) {
    int64_t ret = 1;
    while (p > 0) {
      if (p & 1) (ret *= n) %= m;
      (n *= n) %= m;
      p >>= 1;
    }
    return ret;
  }
}  // namespace haar_lib
#line 6 "Mylib/Graph/Coloring/chromatic_number.cpp"

namespace haar_lib {
  int chromatic_number(const std::vector<std::vector<int>> &graph) {
    static constexpr int mod = 1000000007;
    const int N              = graph.size();

    std::vector<int> g(N);
    for (int i = 0; i < N; ++i) {
      for (auto j : graph[i]) {
        g[i] |= (1 << j);
      }
    }

    std::vector<int64_t> I(1 << N);
    I[0] = 1;
    for (int i = 1; i < (1 << N); ++i) {
      int c = __builtin_ctz(i);
      I[i]  = I[i - (1 << c)] + I[(i - (1 << c)) & (~g[c])];
      if (I[i] >= mod) I[i] -= mod;
    }

    const auto check =
        [&](int k) {
          int64_t t = 0;
          for (int i = 0; i < (1 << N); ++i) {
            if (__builtin_popcount(i) % 2 == 1)
              t -= mod_pow(I[i], k, mod);
            else
              t += mod_pow(I[i], k, mod);
            if (t < 0) t += mod;
            if (t >= mod) t -= mod;
          }
          return (t % mod != 0);
        };

    int lb = 0, ub = N;
    while (std::abs(lb - ub) > 1) {
      const auto mid = (lb + ub) / 2;

      if (check(mid)) {
        ub = mid;
      } else {
        lb = mid;
      }
    }

    return ub;
  }
}  // namespace haar_lib
#line 6 "test/yosupo-judge/chromatic_number/main.test.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, M;
  std::cin >> N >> M;
  std::vector<std::vector<int>> g(N);

  for (int i = 0; i < M; ++i) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  int ans = hl::chromatic_number(g);
  std::cout << ans << "\n";

  return 0;
}

Back to top page