連結成分ごとに完全グラフになっていることが必要十分． DPでの全探索を考える． \(s \in 2^{N}\) に対する答えを \(dp_{s}\) とおく． 連結成分の頂点の選び方さえ決まってしまえば， その内部でどの様に辺を削除したのかは関係ないので， \(s \in 2^{N}\) のdpで解ける． \(dp_{s}\)は，
- 1 (if \(s\)が完全グラフ )
- \(min_{\empty \neq t < s}\) dp_{t} + dp_{s-t}
となる． また， \(\vert s \vert = 0, 1\) のときは完全グラフ．
実装
\(N \leq 18\) と小さいので，bit でグラフをもっておくと， 完全グラフの判定が O(N2^N) で済む．愚直にやるとO(N^2 2^N). \(s\) が元のグラフで完全グラフである判定は， ある \(i \in s\) であって \(t := s - \{i\}\) が完全グラフ かつ \(i\) から \(t\) の全ての頂点に辺がある とできる．
また，DPの遷移において \(s\) の空でない部分集合 \(t\) を全て動くが， これは \(O(3^N)\) で可能． 各頂点 \(i\) に対して，
- \(s,t\) の両方に入る
- \(s\) だけに入る
- どちらにも入らない
の3通りだから． \(t\) にだけ入るというケースは起こらない． 実装は， \(t-- , t = t & s\) の様にする．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
rep(i,m){
ll a,b; cin >> a >> b;
--a, --b;
ed[a] |= 1LL<<b;
ed[b] |= 1LL<<a;
}
vll dp(1LL<<n, INFL);
dp[0] = 1; // dp[0] = 0 とする実装もある．
srep(s,1,1LL<<n){ // if s is exact then dp[s] = 1
rep(i,n) if(s>>i&1){
ll t = s^(1LL<<i);
if(dp[t] == 1 && (ed[i]&t) == t){
dp[s] = 1;
break;
}
}
}
srep(s,1,1LL<<n){
for(ll t = s; t > 0; t--){
t = s & t;
chmin(dp[s], dp[t] + dp[s^t]);
}
}
cout << dp.back() << endl;
return 0;
}
