Party
DP 是门艺术。
\(n\leq 22\) 一眼状压。但是怎么状压就比较困难，因为同一个 \(f[x]\) 可以代表成千上万种含义。
这里我们采用，设 \(f[x]\) 表示当 \(x\) 集合中所有的点都处于同一个团内的最小代价。
则我们有 \(f[x \operatorname{or}sta_i]=\max\limits_{i\in x}\{f[x]+1\}\)。其中 \(sta_i\) 表示与 \(i\) 有边的集合。
初始为 \(f[\{i\}]=0\)，其它均为 \(+\infty\)。
复杂度为 \(O(n2^n)\)。
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f;
const int N=22;
int n,m,maxx,x,y;
int f[1<<N],d[1<<N],b[1<<N],st[N];
stack<int>s;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
maxx=(1<<n);
memset(f,INF,sizeof(f));
for(int i=1;i<=m;i++){
cin>>x>>y;
x--;y--;st[x]|=(1<<y);st[y]|=(1<<x);
}
if(m*2==n*(n-1)){cout<<"0";return 0;}
for(int i=0;i<n;i++) f[1<<i]=0;
for(int u=1;u<maxx;u++){
for(int i=0;i<n;i++){
if(!(u&(1<<i))) continue;
int v=u|st[i];
if(v==u) continue;
if(f[v]>f[u]+1){
f[v]=f[u]+1;
d[v]=u;
b[v]=i;
}
}
}
cout<<f[maxx-1]<<'\n';
int t=maxx-1;
while(__builtin_popcount(t)!=1){s.push(b[t]);t=d[t];}
while(!s.empty()){cout<<s.top()+1<<" ";s.pop();}
return 0;
}