DFSとBit全探索について解説 [競プロ]

はじめに

筆者はレート1桁の雑魚です。REを一生直せないのですが、アルゴリズムの理解が完璧であることを自己証明するために記事を書いています。ご了承ください。

DFSとは

日本語では深さ優先探索と言います。無向グラフの様子を調べたりする時に使います。
詳しくはこちらの記事で解説されてます。

やり方は単純です。

1. 全部のノードから始める
2. 通った場所を無効にする
3. 繋がっているノードに進む
4. 通ってない場所がなくなった時に終了する

通ったかどうかはboolean値で表現します。
なので、ノードの数をNとした時に、2^Nのlong longで管理可能です。
それがBitの使い道です。

Bit演算についてちょいと解説

演算記号をおさらい

aの該当箇所の数値をいじる

a |= (1 << b); //b-indexを1にする
a &= ~(1 << b); //b-indexを0にする

便利なライブラリをご紹介

2進数表現のときの1の数を返す

#include <bits/stdc++.h>
int popcount = std::__builtin_popcount(target);

2進数表現のときの一番左側にくる1のindexを返す

#include <bits/stdc++.h>
int firstIndexOne = std::__builtin_ctz(target);

・全部探索してない(初期化時)の方法

// 2^N - 1と同等; Nが8の時に 01111111となる.
int explored = (1 << N) - 1;

具体例

ABC002Dを解いています。

問題：
・ノードの数とその接続状況が渡される
・一番大きい集合のノード数(最大クリーク)を返してください

やり方：
・vector(N)でそれぞれのノードの接続状況を2進数表現で格納する
・再帰的に全ノードから調べさせる　次の行き先の候補は現在地のノードの接続状況から絞る

コード(RuntimeErrorで動かない...)

ABC002D

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
  int N, M; cin>>N>>M;
  vector<int> v(N, 0);
  for(int i=0; i<M; ++i) {
    int x, y; cin>>x>>y; 
    --x; --y;
    v[x] |= (1LL << y);
    v[y] |= (1LL << x);
  }
  for (int i = 0; i < N; ++i) v[i] |= (1LL << i);
  
  int max_clique = 0;
  auto dfs = [&](int subset, int candidates, const vector<int>& adj) {
    if(candidates==0) {
      max_clique = max(max_clique, __builtin_popcountll(subset));
      return;
    }
    while (candidates) {
      int i = __builtin_ctzll(candidates);
      candidates &= ~(1LL << i);
      dfs(subset | (1LL << i), candidates & adj[i], adj);
    }
  };
  
  dfs(0, (1LL << N)-1, v);
  cout << max_clique << endl;
  
  return 0;
}

まとめ

僕なりに要点に絞ったので、わかりやすかったのではないでしょうか？
ただ、このコードのどこかに眠るエラーのせいで、問題を解くことはできないので、ご了承ください。
(編集リクエスト通しますので、もしよければデバッグ代行してください！)

ここまでお疲れ様でした。