隐隐感觉N年前做过一道类似的题。
很显然我们只需要考虑，仅有0边的子图有多少个连通块，然后这个数量减去1就是答案了(这个和kruscal过程等价)。
然后其实就是妥妥的暴力了。。。因为1边数量非常之少，于是我们就可以直接每次暴力合并两个连通块。
显然这里判断是否能合并的 总复杂度是 O(M)的，因为不同阶段连通块的判断不会用到同一条边，而只要两个连通块中有一条不是1的边就可合并；
合并的复杂度的话，启发式合并可以做到 O(N log N)。
于是就愉快的做完了，代码还超好写233
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pb push_back
const int N=100005;
unordered_map<int,int> mmp[N];
vector<int> g[N];
int n,p[N],m,U,V,sz;
int getfa(int x){ return p[x]==x?x:(p[x]=getfa(p[x]));}
inline bool can(int x,int y){
for(int i:g[x])
for(int j:g[y]) if(!mmp[i][j]) return 1;
return 0;
}
inline void Merge(int x,int y){
if(g[x].size()>g[y].size()) swap(g[x],g[y]);
for(int i:g[x]) g[y].pb(i);
}
inline void solve(){
for(int i=1;i<=n;i++) g[i].pb(i),p[i]=i;
for(int i=n;i;i--){
bool flag=0;
for(int j=i-1;j;j--) if(can(i,j)){
Merge(i,j),flag=1;
break;
}
sz-=flag,g[i].clear();
}
}
int main(){
for(scanf("%d%d",&n,&m),sz=n;m;m--) scanf("%d%d",&U,&V),mmp[U][V]=mmp[V][U]=1;
solve(),printf("%d\n",sz-1);
return 0;
}
原文：https://www.cnblogs.com/JYYHH/p/11965817.html