Description
FGD开办了一家电话公司。他雇用了N个职员,给了每个职员一部手机。每个职员的手机里都存储有一些同事的
电话号码。由于FGD的公司规模不断扩大,旧的办公楼已经显得十分狭窄,FGD决定将公司迁至一些新的办公楼。FG
D希望职员被安置在尽量多的办公楼当中,这样对于每个职员来说都会有一个相对更好的工作环境。但是,为了联
系方便起见,如果两个职员被安置在两个不同的办公楼之内,他们必须拥有彼此的电话号码。
Input
第一行包含两个整数N(2<=N<=100000)和M(1<=M<=2000000)。职员被依次编号为1,2,……,N.以下M行,每
行包含两个正数A和B(1<=A<b<=n),表示职员a和b拥有彼此的电话号码),li <= 1000
Output
包含两行。第一行包含一个数S,表示FGD最多可以将职员安置进的办公楼数。第二行包含S个从小到大排列的
数,每个数后面接一个空格,表示每个办公楼里安排的职员数。
Sample Input
7 16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7
Sample Output
3
1 2 4
HINT
FGD可以将职员4安排进一号办公楼,职员5和职员7安排进2号办公楼,其他人进3号办公楼。
给一个图,图中没有边相连的就必须在同一栋楼里,反过来想,不就是求补图的连通块嘛,但是这题数据很大,建不了图,看了题解的骚操作,用模拟链表来优化bfs
就是先创建一个队列,把所有点都加进去,然后从链表中取出点进行bfs,标记相邻的边,这些边就不是同一个连通分量的,所以把没标记的边也就是同一个连通分量的从链表中删去,这样就达到优化的效果
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=100050;
const int M=4000050;
struct Edge{
int v,next;
}edge[M];
int cnt,head[N];
void init(){
cnt=0;
memset(head,-1,sizeof(head));
}
void addEdge(int u,int v){
edge[cnt]=Edge{
v,head[u]};
head[u]=cnt++;
edge[cnt]=Edge{
u,head[v]};
head[v]=cnt++;
}
int n,m,u,v;
//链表
int pre[N],nex[N];
//连通块
int ans,num[N];
//队列
int q[N];
bool flag[N];
void del(int x){
nex[pre[x]]=nex[x];
pre[nex[x]]=pre[x];
}
void bfs(int x){
//模拟队列
int hea=0,tai=1;
q[0]=x;
while(hea<tai){
num[ans]++;
int u=q[hea++];
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
//标记一下相连的边,后边删除没连的边
flag[v]=true;
}
for(int i=nex[0];i<=n;i=nex[i]){
//删除链表中未标记的点并入队
if(!flag[i]){
del(i);
q[tai++]=i;
}
}
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
flag[v]=false;
}
}
}
int main(void){
scanf("%d%d",&n,&m);
init();
while(m--){
scanf("%d%d",&u,&v);
addEdge(u,v);
}
//双向链表
for(int i=0;i<=n;i++){
nex[i]=i+1;
}
for(int i=1;i<=n+1;i++){
pre[i]=i-1;
}
//遍历链表
for(int i=nex[0];i<=n;i=nex[0]){
//对一个链表中的点进行bfs,每次遍历与他不相邻的点
//在补图中就是同一个连通块,所以标记这些不相邻的点并在链表中删除
del(i);
//连通块++
ans++;
bfs(i);
}
printf("%d\n",ans);
sort(num+1,num+ans+1);
for(int i=1;i<=ans;i++){
printf("%d ",num[i]);
}
printf("\n");
return 0;
}