Codeforces Round #599 (Div. 2) D.0-1 MST(补图连通块/并查集)

题目

给一个n(n<=1e5)个，点m(m<=n*(n+1)/2)条边的图，

图本是完全图，这m条边的代价都为1，其余的边的代价都为0，

求这个图的最小生成树的代价，输出代价

思路来源

官方题解

题解1

考虑把0边的在并查集都合在一起，忽略1边，就变成了补图x个连通块，

使x个联通块相同必须用1的代价，答案即补图连通块个数-1，

一条边只在点号大的时候考虑一次，对于一个给定点u，

如果u连向另一连通块v的1边的个数now[v]比这个连通块的大小sz[v]要小，

说明u一定有0边连向这个连通块v，即合并u和v的集合

检查所有边，每次并查集合并复杂度logn，总复杂度大概O(nlogn+m)

代码1

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,m,u,v,x,y;
int sz[N],par[N];
int rt[N],tot,num;//rt[]:满足par[i]==i的集合
int now[N],ans;//now[i]:现在的点的个数
vector<int>e[N];
int find(int x)
{
return par[x]==x?x:par[x]=find(par[x]);
}
int main()
{
//求补图连通块的块数
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
par[i]=i;
sz[i]=1;
}
for(int i=1;i<=m;++i)
{
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;++i)
{
for(int v:e[i])
{
if(v>i)continue;
now[find(v)]++;
}
for(int j=1;j<=tot;++j)//1-tot为已出现的点 rt[j]为现存的根
{
x=find(rt[j]);
y=find(i);
if(x==y)continue;
if(sz[x]>now[x])
{
par[y]=x;
sz[x]+=sz[y];
}
}
num=0;
for(int j=1;j<=tot;++j)
if(find(rt[j])==rt[j])rt[++num]=rt[j];
if(find(i)==i)rt[++num]=i;
tot=num;
for(int v:e[i])
{
if(v>i)continue;
now[find(v)]=0;
}
}
for(int i=1;i<=n;++i)
if(find(i)==i)ans++;
printf("%dn",ans-1);
return 0;
} 

题解2

做法是bfs，set维护当前没有确定集合的点，确定了一个点即将其删掉，

此做法复杂度比较玄学，据说均摊O(nlogn+nlogm)

其实不是愁没有做法，只是不敢莽啊，分析不出确切复杂度，参考一下qls的代码吧

但感觉好像最坏情况应该是sqrt个块，每个内部完全图的情形，这样好像也只是nsqrt(n)的样子？

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
bool vis[MAXN],ban[MAXN];
list<int> fre;
vector<int> e[MAXN];
int bfs(int st)
{
int res=0;
queue<int> q;
q.push(st);
while(!q.empty())
{
int u=q.front();
q.pop();
if(vis[u])continue;
vis[u]=1,res++;
for(auto &v:e[u])ban[v]=1;
for(auto itr=fre.begin();itr!=fre.end();)
{
int v=*itr;
if(!ban[v])
{
q.push(v);
fre.erase(itr++);
}
else itr++;
}
for(auto &v:e[u])ban[v]=0;
}
return res;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
fre.push_back(i);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
vector<int> con;
for(int i=1;i<=n;i++)
if(!vis[i])con.push_back(bfs(i));
sort(con.begin(),con.end());
printf("%dn",(int)con.size()-1);
return 0;
}

最后

以上就是时尚小猫咪为你收集整理的Codeforces Round #599 (Div. 2) D.0-1 MST(补图连通块/并查集)的全部内容，希望文章能够帮你解决Codeforces Round #599 (Div. 2) D.0-1 MST(补图连通块/并查集)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。