题解 CF1242B 【0-1 MST】

· · 题解

水题，直接暴力就能过

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

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

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

那么怎么求联通快呢?

直接dfs是可以的！

但是需要剪枝

最短代码

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

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

#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);
}