説明

グラフの最大独立集合を求める。一般グラフに対する最大独立集合を求める問題はNP困難である。

補グラフに対する最大クリーク問題と等価である。

乱択でもつよい　よわかったらほかの強い人のライブラリを使うべき

計算量

うく

実装例

  • maximum_independent_set($g$, $trial=1000000$):= 隣接行列 $g$ で表されるグラフの最大独立集合を求める。
template< typename T >
vector< int > maximum_independent_set(const Matrix< T > &g, int trial = 1000000) {

  int N = (int) g.size();
  vector< uint64_t > bit(N);

  assert(N <= 64);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(i != j) {
        assert(g[i][j] == g[j][i]);
        if(g[i][j]) bit[i] |= uint64_t(1) << j;
      }
    }
  }

  vector< int > ord(N);
  iota(begin(ord), end(ord), 0);
  mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  int ret = 0;
  uint64_t ver;
  for(int i = 0; i < trial; i++) {
    shuffle(begin(ord), end(ord), mt);
    uint64_t used = 0;
    int add = 0;
    for(int j : ord) {
      if(used & bit[j]) continue;
      used |= uint64_t(1) << j;
      ++add;
    }
    if(ret < add) {
      ret = add;
      ver = used;
    }
  }
  vector< int > ans;
  for(int i = 0; i < N; i++) {
    if((ver >> i) & 1) ans.emplace_back(i);
  }
  return ans;
}

検証

AtCoder CODE THANKS FESTIVAL 2017 G - Mixture Drug

int main() {
  int N, M;
  cin >> N >> M;
  Matrix< int > g(N, vector< int >(N));
  for(int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x][y] = g[y][x] = true;
  }
  cout << maximum_independent_set(g).size() << endl;
}