graph/max-independent-set.hpp

• View this file on GitHub
• Last update: 2020-12-05 07:59:51+09:00
• Include: #include "graph/max-independent-set.hpp"

Verified with

• verify/verify-yosupo-graph/yosupo-max-independent-set.test.cpp

Code

#pragma once

template <int m>
vector<int> max_independent_set(const vector<vector<int>> &g) {
  constexpr int M = (m + 63) / 64 * 64;
  int N = g.size();
  vector<bitset<M>> bs(N);
  for (int i = 0; i < N; i++)
    for (auto &j : g[i]) bs[i][j] = bs[j][i] = 1;
  bitset<M> res, cur, ignore;
  auto dfs = [&](auto rec, int i) -> void {
    if (i == N) {
      if (cur.count() > res.count()) res = cur;
      return;
    }
    if ((bs[i] & cur).any() || (bs[i] & ~ignore).count() >= 2) {
      ignore[i] = 1;
      rec(rec, i + 1);
      ignore[i] = 0;
    }
    if ((bs[i] & cur).none()) {
      cur[i] = 1;
      rec(rec, i + 1);
      cur[i] = 0;
    }
  };
  dfs(dfs, 0);
  vector<int> res2;
  for (int i = 0; i < N; i++)
    if (res[i]) res2.push_back(i);
  return res2;
}

#line 2 "graph/max-independent-set.hpp"

template <int m>
vector<int> max_independent_set(const vector<vector<int>> &g) {
  constexpr int M = (m + 63) / 64 * 64;
  int N = g.size();
  vector<bitset<M>> bs(N);
  for (int i = 0; i < N; i++)
    for (auto &j : g[i]) bs[i][j] = bs[j][i] = 1;
  bitset<M> res, cur, ignore;
  auto dfs = [&](auto rec, int i) -> void {
    if (i == N) {
      if (cur.count() > res.count()) res = cur;
      return;
    }
    if ((bs[i] & cur).any() || (bs[i] & ~ignore).count() >= 2) {
      ignore[i] = 1;
      rec(rec, i + 1);
      ignore[i] = 0;
    }
    if ((bs[i] & cur).none()) {
      cur[i] = 1;
      rec(rec, i + 1);
      cur[i] = 0;
    }
  };
  dfs(dfs, 0);
  vector<int> res2;
  for (int i = 0; i < N; i++)
    if (res[i]) res2.push_back(i);
  return res2;
}

Back to top page