CF920E Connected Components?

先讲两个靠谱的做法

1.首先因为有n个点,m条不存在的边,所以至少存在一个点,和m/n个点之间没边,所以把这个点找出来,连一下其他相连的点,这样还剩m/n个点没确定在哪个联通块,而这些点最多和n-1个点有边,所以从这些点暴力合并即可

2.开一个队列/set/链表维护没有确定在哪个联通块的边,每次先取出一个点,然后往点集里尽量连边,再把连出的点放到队列里继续连边合并,这样每次都能搜出一个联通块

下面是假算法

每次找一个没标记的点,打标记,爆枚所有存在的边,和对应点连上,在把刚刚扫到的点打标记

然额是错的,详见我的提交记录

但是懒得改了

#include<bits/stdc++.h>

#define LL long long

#define db double

#define il inline

#define re register

using namespace std;

const int N=2e5+10;

il LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int to[N<<1],nt[N<<1],hd[N],dg[N],tot=1;

il void add(int x,int y)

{

    ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot,--dg[x];

    ++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot,--dg[y];

}

bool v[N],vv[N];

int n,m,ff[N],sz[N],s[N],a[N],ta;

il int findf(int x){return ff[x]==x?x:ff[x]=findf(ff[x]);}

il bool cmp(int a,int b){return dg[a]>dg[b];}

int main()

{

	n=rd(),m=rd();

	for(int i=1;i<=n;++i) ff[i]=i,sz[i]=1,dg[i]=n-1,s[i]=i;

	for(int i=1;i<=m;++i) add(rd(),rd());

	sort(s+1,s+n+1,cmp);

	for(int i=1;i<=n;++i)

		if(!v[s[i]]||n<=5000)    //把数据小的部分暴力处理就能过了qwq

		{

			v[s[i]]=vv[s[i]]=1;

			for(int j=hd[s[i]];j;j=nt[j]) vv[to[j]]=1;

			for(int j=1;j<=n;++j)

				if(!vv[j])

				{

					v[j]=1;

					int x=findf(s[i]),y=findf(j);

					if(x^y) ff[y]=x,sz[x]+=sz[y];

				}

			vv[s[i]]=0;

			for(int j=hd[s[i]];j;j=nt[j]) vv[to[j]]=0;

		}

	for(int i=1;i<=n;++i)

		if(findf(i)==i) a[++ta]=sz[i];

	sort(a+1,a+ta+1);

	printf("%d\n",ta);

	for(int i=1;i<=ta;++i) printf("%d ",a[i]);

    return 0;

}

巴特西

CF920E Connected Components?

最新文章

热门文章