题意

给$n$个点（$n\le 18$），$m$条边（$m\le \frac{n\ast (n-1)}{2}$）你一个简单无向图，删去一些边（可以是0），使得图满足以下性质：

• 任意两点$a$，$b$，如果$a$，$b$连通，那么$a$，$b$之间有边。

求满足条件最少的连通块数量。

思路

题目数据很小，状压走起！

首先我们设$f_v$表示当顶点集合为$v$时，最少的连通块数量。

然后我们先暴力枚举点集$v$，判断这个点集$v$是否为完全图。

此时我们想怎么转移。

我们可以发现当$v^{\prime }$为$v$的子集时，$f_v=min(f_{v^{\prime }}+f_{v-v^{\prime }})$。

所以此时我们就要枚举$v^{\prime }$。

我们先把$v^{\prime }=v$，然后我们接下来每次都把$v^{\prime }=(v^{\prime }-1)\&v$，此时$(v^{\prime }-1)\&v$肯定是$v$的子集，因为如果$v^{\prime }-1$中二进制下有一位为$1$且$v$的这一位为$0$，那么在$(v^{\prime }-1)\&v$的时候这个$1$就不见了，因为$1\&0=0$。

接下来我们来算一下时间复杂度。

在枚举$v^{\prime }$的时候，因为$v$和$v^{\prime }$的在二进制下每一位的关系只有三种情况，$1/0$，$1/1$，$0/0$，也就是说，把所有枚举的情况乘起来，就是$3^n$，虽然$3^n\ge 3\times 10^9$，但是因为常数很小，所以还是可以过。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,mp[25][25],f[2621445];
int main() {
    int u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&u,&v),mp[u][v]=mp[v][u]=1;
    bool flag;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=(1<<n)-1;i++) {
        flag=true;
        for(int j=1;j<n;j++)
            if((i>>(j-1))&1)
                for(int l=j+1;l<=n;l++)
                    if((i>>(l-1))&1&&(!mp[j][l])) {
                        flag=false;
                        break;
                    }
        if(flag)
            f[i]=1;
    }
    for(int i=1;i<=(1<<n)-1;i++)
        for(int j=i;j;j=(j-1)&i)
            f[i]=min(f[i],f[j]+f[i^j]);
    printf("%d",f[(1<<n)-1]);
    return 0;
}