P3452 [POI2007]办公室

2018-07-08 20:44:08


这题妙啊

题意:给定一张无向图,将n个点分成若干个集合,使得任意分属两个集合的点对之间

都有边直接相连。求最多分成的集合数量以及每个集合中的点数

一开始想直接枚举点暴力,发现数据范围1e5,放弃了

想到bfs却又没什么具体实现方法

看到题解才想到链表和bfs结合的思路

实在是妙啊

显然,对于一个已知起点,与它没有边相连的点一定和它属于同一集合

根据这一点,就可以从不同的点分别进行bfs

在bfs中如果直接从1枚举到n,显然复杂度不可接受

这就用到了链表:每一个点入队时,将其从链表中删去,保证下一次不再访问到,加快

了枚举的速度,避免了最后一个点TLE的尴尬

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5,M=2e6+5;
struct node
{
    int to,nxt;
}edge[M<<1];
int n,m,num,cnt,head[N],ans,res[N],nxt[N],pre[N];
bool vis[N],exist[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
inline void del(int k)
{
    nxt[pre[k]]=nxt[k];
    pre[nxt[k]]=pre[k];
}
inline void bfs(int k)
{
    queue<int>q;
    q.push(k); vis[k]=1; del(k); cnt=1;
    while (!q.empty())
    {
        int u=q.front(); q.pop();
        memset(exist,0,sizeof(exist));
        for (reg int i=head[u];i;i=edge[i].nxt) exist[edge[i].to]=1;
        for (reg int i=nxt[0];i<=n;i=nxt[i])
          if (!exist[i]) q.push(i),vis[i]=1,++cnt,del(i);
    }
    res[++ans]=cnt;
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        add_edge(x,y);
        add_edge(y,x);
    }
    for (reg int i=1;i<=n;i++) pre[i]=i-1,nxt[i]=i+1;
    for (reg int i=1;i<=n;i++) if (!vis[i]) bfs(i);
    printf("%d\n",ans);
    sort(res+1,res+ans+1);
    for (reg int i=1;i<=ans;i++) printf("%d ",res[i]);
    return 0;
}