「CF1242B」0-1 MST

题意：有一张完全图，$n(1\leq n\leq 10^5)$ 个节点有 $m(0\leq m\leq 10^5)$ 条边的边权为 $1$，其余的都为 $0$，这 $m$ 条边会给你，问你这张图的最小生成树的权值。

一道很有趣的思维题。

很明显我们不可能暴力用最小生成树的算法求解，但是我们可以发现一个有趣的性质：

如果我们只走所有边权为 $0$ 的边，那么所得到的连通块个数减 $1$ 就是答案。

这是很明显成立的，因为把这些连通块之间用边权为 $1$ 的边合起来才能使整块图连通，这些边权为 $1$ 的边肯定会在最小生成树上。

但是由于不能把所有边权为 $0$ 的边存下来，所以我们只用存边权为 $1$ 的边，用一个 set 存储没被访问过的点，一开始把所有点加进去，每次访问时都把能走到的所有边(我们可以用 map 存储边，这样在找边权为 $0$ 的边时可以直接调用 find 函数)中，边权为 $0$ 到达的点从 set 中删去(这里可以用一个 vector 记录要被删除的点)，看看这样访问几次能把 set 删空，得到的便是连通块个数。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans;
map<int,int> s[101010];//存边
set<int> k;//存储还没有访问的点
void dfs(int u)
{
	set<int>::iterator it;
	vector<int> q;//存储这次遍历中边权为0到达的点，可以组成一个连通块
	for(it=k.begin();it!=k.end();it++)//遍历没访问的点
		if(s[u].find(*it)==s[u].end())//如果没有在存的1边中找到，说明是0边
			q.push_back(*it);
	for(int i=0;i<(int)q.size();i++)
		k.erase(q[i]);//遍历了，加入连通块，删除
	for(int i=0;i<(int)q.size();i++)
		dfs(q[i]);//继续搜索
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		s[a][b]=1;
		s[b][a]=1;
	}
	for(int i=1;i<=n;i++)
		k.insert(i);
	while(!k.empty())
	{
		int u=*k.begin();
		k.erase(u);//取出还在其中的点，删除，准备访问；
		dfs(u);
		ans++;
	}
	printf("%d",ans-1);
	return 0;
}