な bit DP としてよく知られている問題ですね！
EDPC U - Grouping の類題と言える！
atcoder.jp
問題概要
頂点数 
、辺数 
の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラフがいずれもクリークとなるようにしたい。
分割されたグループの個数の最小値を求めよ。
制約
解法 (1)： の bit DP
こんな bit DP をすれば OK！！！
dp[bit] ← bit に対応する頂点集合をいくつかのクリークに分割するとき、分割されたクリークの個数の最小値
そして遷移は次の通り。
chmin(dp[bit | add], dp[bit] + 1);
これは一見すると、bit が 
通りあって、そのそれぞれに対して add が 
通りあって、全体で 
通りに思えてしまうかもしれない。しかし実はちゃんと解析すると となって十分間に合うのだ。具体的には
「add は、bit の補集合の部分集合しか動かない」
という点に着目する。実装上はこんな感じにできる。ここで、「部分集合の部分集合を列挙する方法」を活用している。
for (int bit = 0; bit < (1<<N); ++bit) {
int cbit = (1<<N) - 1 - bit;
for (int add = cbit; ; add = (add-1) & cbit) {
if (!add) break;
if (ok[add]) chmin(dp[bit|add], dp[bit] + 1);
}
}
この処理の計算量が であることを示そう。実は簡単だ。(bit, add) のとりうる値は次のように考えると 
通りしかない。各頂点 
について、
- 頂点
は頂点集合 bit に含まれる
- 頂点 は頂点集合 bit に含まれないが、頂点集合 add に含まれる
- 頂点 は頂点集合 bit, add のいずれにも含まれない
という 3 パターンしかない。したがって、考えられる状況は 通りなのだ。以上から、今回の bit DP の計算量が であることがわかった。
コード
前処理として、以下の配列を求めている。
ok[bit] ← 頂点集合 bit がクリークかどうか
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int main() {
int N, M;
cin >> N >> M;
vector<vector<int>> G(N, vector<int>(N, false));
for (int i = 0; i < M; ++i) {
int a, b; cin >> a >> b; --a, --b;
G[a][b] = G[b][a] = true;
}
vector<bool> ok(1<<N, true);
for (int bit = 0; bit < (1<<N); ++bit) {
vector<int> vs;
for (int i = 0; i < N; ++i) if (bit & (1<<i)) vs.push_back(i);
for (int i = 0; i < vs.size() && ok[bit]; ++i) {
for (int j = i+1; j < vs.size() && ok[bit]; ++j) {
if (!G[vs[i]][vs[j]]) ok[bit] = false;
}
}
}
const int INF = 1<<29;
vector<int> dp(1<<N, INF);
dp[0] = 0;
for (int bit = 0; bit < (1<<N); ++bit) {
if (dp[bit] >= INF) continue;
int cbit = (1<<N) - 1 - bit;
for (int add = cbit; ; add = (add-1) & cbit) {
if (!add) break;
if (ok[add]) chmin(dp[bit|add], dp[bit] + 1);
}
}
cout << dp[(1<<N)-1] << endl;
}
解法 (2)：補グラフの彩色数
クリークといえば、補グラフをとれば「安定集合」になる。安定集合とは、
「頂点集合の部分集合であって、どの 2 頂点間にも辺がないようなもの」
のことを指す。クリークを見たら補グラフをとるのはありかもしれない。さて、もとのグラフで同一のグループの頂点は同じ色で塗り、異なるグループの頂点は異なる色で塗るとしたとき、
- もとのグラフで条件を満たしている場合、同じ色の頂点間にはすべて辺があるので、補グラフでは辺彩色 (同じ色の頂点間には辺がない) になっている
- 補グラフで辺彩色になっている場合、同じ色の頂点間にはすべて辺がないので、もとのグラフでは同じ色の頂点間にはすべて辺がある
というふうになっている。つまり、補グラフの彩色数を求めれば OK。補グラフの彩色数は次の記事で書いた。計算量は 
でできる！
drken1215.hatenablog.com
コード
#include <bits/stdc++.h>
using namespace std;
long long modpow(long long a, long long n, long long MOD) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % MOD;
a = a * a % MOD;
n >>= 1;
}
return res;
}
int chromatic_number(const vector<vector<int> > &G) {
const int MOD = 1000000007;
int n = (int)G.size();
vector<int> neighbor(n, 0);
for (int i = 0; i < n; ++i) {
int S = (1<<i);
for (int j = 0; j < n; ++j)
if (G[i][j])
S |= (1<<j);
neighbor[i] = S;
}
vector<int> I(1<<n);
I[0] = 1;
for (int S = 1; S < (1<<n); ++S) {
int v = __builtin_ctz(S);
I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]];
}
int low = 0, high = n;
while (high - low > 1) {
int mid = (low + high) >> 1;
long long g = 0;
for (int S = 0; S < (1<<n); ++S) {
if ((n - __builtin_popcount(S)) & 1) g -= modpow(I[S], mid, MOD);
else g += modpow(I[S], mid, MOD);
g = (g % MOD + MOD) % MOD;
}
if (g != 0) high = mid;
else low = mid;
}
return high;
}
int main() {
int N, M;
cin >> N >> M;
vector<vector<int>> G(N, vector<int>(N, 1));
for (int i = 0; i < M; ++i) {
int a, b; cin >> a >> b; --a, --b;
G[a][b] = G[b][a] = 0;
}
cout << chromatic_number(G) << endl;
}
人いる
人いる
票を獲得する (青木派は裏切り者)
でソートの町に行っただけでは「高橋君: 100、青木君: 101」となってダメ
の町に 1 個行くだけで、「高橋君: 99、青木君: 91」となるので OK
である
だけ減少する
