当前位置 博文首页 > Q755100802的博客:Codeforce round 599 D. 0-1 MST (补图+BFS+
题目链接:https://codeforces.com/contest/1243/problem/D
给定一个n节点的完全图(n<=1e5),现在给出m条边权为1的边(m<=min(n*(n-1)/2,1e5)),其余的边权值为0,问你这个图的最小生成树的权值大小是多少?
很明显,如果我们考虑边权为0的边并去掉边权为1的边,那么答案就是边权为0的边组成的连通块个数-1。
现在需要求补图的连通块,不能考虑边,因为边实在太多了,所以我们直接用点做就好了,从每个未被访问的点开始BFS一下,如
果u到v有为0的路径,将v标记一下并且以后再也不访问它,这样复杂度就降下来了。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
set<int>s;
set<int>G[maxn];
int vis[maxn];
void BFS(int x){
s.erase(x);
vis[x]=1;
queue<int>Q;
Q.push(x);
while(Q.size()){
int u=Q.front();Q.pop();
for(auto it=s.begin();it!=s.end();){
int v=*it++;
if(!G[v].count(u)){
//说明u,v在原图中并没有相连,是补图中的边
s.erase(v);
Q.push(v);
vis[v]=1;
}
}
}
}
signed main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
s.insert(i);
}
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].insert(v);
G[v].insert(u);
}
int ans=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
BFS(i);
ans++;
}
}
printf("%d\n",ans-1);
return 0;
}
?
cs