题解 CF920E 【Connected Components?】

142857cs · 2018-06-09 21:58:48 · 题解

删去的边数只有m条，所以至少存在一个点，删去的与它连接的边的条数不超过m/n。

找出这个点，然后找出所有与这个点有边相邻的点，将它们合并成一个连通块。

显然，连通块内部的边不用考虑，需要考虑的边一定与连通块外的某个点相连。

连通块外最多只有m/n个点，每个点最多与n条边相连，所以这样的边最多只有m条，暴力即可

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int head[262144],last[524288],to[524288],cnt=0;
int fa[262144];
int deg[262144];
bool vis[262144];
bool vis2[262144];
int sb[262144];
int sz[262144];
void add(int u,int v)
{
    cnt++;
    last[cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    deg[v]++;
}
int findroot(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    return fa[x]=findroot(fa[x]);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    int u=0,md=n;
    for(int i=1;i<=n;i++)
    {
        if(deg[i]<md)
        {
            md=deg[i];
            u=i;
        }
    }
    for(int i=head[u];i;i=last[i])
    {
        vis[to[i]]=true;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            fa[i]=u;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            continue;
        }
        memset(vis2,0,sizeof(vis2));
        int x=findroot(i);
        for(int j=head[i];j;j=last[j])
        {
            vis2[to[j]]=true;
        }
        for(int j=1;j<=n;j++)
        {
            if(vis2[j])
            {
                continue;
            }
            int y=findroot(j);
            fa[y]=x;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i)
        {
            sb[i]=ans;
            ans++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        sz[sb[findroot(i)]]++;
    }
    sort(sz,sz+ans);
    printf("%d\n",ans);
    for(int i=0;i<ans;i++)
    {
        printf("%d",sz[i]);
        if(i==ans-1)
        {
            putchar('\n');
        }
        else
        {
            putchar(' ');
        }
    }
    return 0;
}