CF1242B 0-1 MST 题解

发表于 分类于

本文迁移自洛谷原文。

水题，直接暴力就能过

由于图很大，所以就不能直接连边最小生成树

所以我们可以换一个角度考虑:

求出所有可以用0边连成的联通块，那么将这些联通快连起来，就可以构造出一颗最小生成树

那么怎么求联通快呢?

直接dfs是可以的！

但是需要剪枝

最短代码

set s:还有哪些点没有被访问过
由于只有一些边是1边，所以几次下来，就几乎全访问过了

map<int,int> g[]: 存所有的1边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
map<int,int>g[200005];
set<int>s,ns;
inline void dfs(int x){
	vector<int>v;v.clear();ns.clear();
	for(set<int>::iterator it=s.begin();it!=s.end();it++)if(!g[x][*it])v.push_back(*it);else ns.insert(*it);  //只用在没有经过的点中找
	s=ns;//更新
  for(int i:v)dfs(i);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;++i)scanf("%d%d",&u,&v),g[u][v]=1,g[v][u]=1;
	for(int i=1;i<=n;++i)s.insert(i);
	for(;s.size();){++cnt;int t=*s.begin();s.erase(t);dfs(t);}
	printf("%d\n",cnt-1);
}