Graph vertex coloring
(Mylib/Graph/Coloring/chromatic_number.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• chromatic_number(g)
  • Time complexity $O(2^n \log^2 n)$

Requirements

Notes

Problems

• AOJ 2136 Webby Subway
• AOJ 1254 Color the Map

References

Depends on

• Mod pow (Mylib/Number/Mod/mod_pow.cpp)

Verified with

• test/aoj/2136/main.test.cpp
• test/yosupo-judge/chromatic_number/main.test.cpp

Code

#pragma once
#include <cmath>
#include <cstdint>
#include <vector>
#include "Mylib/Number/Mod/mod_pow.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 2 "Mylib/Graph/Coloring/chromatic_number.cpp"
#include <cmath>
#include <cstdint>
#include <vector>
#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

Back to top page