1098: [POI2007]办公楼biu
Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 640 Solved: 254
[Submit][Status][Discuss]
Description
一些员工，每个人知道另外一些人的电话号码。假如A知道B的电话，B也一定知道A的电话号。上司想把这些员工分到尽可能多的办公楼里去。但是，如果A和B不在同一办公楼内，A和B就必须有对方的电话号码。求这些员工最多能够被分到多少办公楼内，并升序输出每个办公楼内的员工人数。
Input
第一行包含两个整数N（2<=N<=100000）和M（1<=M<=2000000）。职员被依次编号为1,2,……,N. 以下M行，每行包含两个正数A和B(1<=A<b<=n)，表示职员a和b拥有彼此的电话号码。
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
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
1 2 4
HINT
FGD可以将职员4安排进一号办公楼，职员5和职员7安排进2号办公楼，其他人进3号办公楼。
首先求出原图补图，则要求转化为-不同办公楼的人不连边。
于是想到求其补图连通块-显然补图是稠密图，会T
这题要用链表优化Dfs.
正常情况下我们从Node 1枚举到Node N ，会TLE
所有不妨建立链表，当一个元素走后便删掉
这样效率便转化为O(n+m)
Ps:这题用cin和scanf效率差很多
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<list>
using namespace std;
#define MAXN (100000+10)
#define MAXM (2000000+10)
int n,m;
int size=0,edge[MAXM*2],pre[MAXM],next[MAXM*2];
struct link
{
int pre,next;
}l[MAXN];
void del(int x)
{
l[l[x].pre].next=l[x].next;
l[l[x].next].pre=l[x].pre;
}
queue<int> q;
void addedge(int u,int v)
{
edge[++size]=v;
next[size]=pre[u];
pre[u]=size;
}
bool b[MAXN],q_b[MAXN];
int z[MAXN],siz_z=0;
void bfs()
{
memset(b,0,sizeof(b));
memset(q_b,0,sizeof(q_b));
while (l[0].next)
{
int now=l[0].next,ans=1;
del(now);
q.push(now);q_b[now]=1;
//cout<<now<<endl; //00x
while (!q.empty())
{
int u=q.front();q.pop();
for (int p=pre[u];p;p=next[p]) b[edge[p]]=1;
for(int i=l[0].next;i;i=l[i].next)
{
if (!b[i]&&!q_b[i])
{
q_b[i]=1;
q.push(i);//cout<<v<<endl; //0xx
ans++;
del(i);
}
}
for (int p=pre[u];p;p=next[p]) b[edge[p]]=0;
// cout<<endl;
}
z[++siz_z]=ans;
}
}
int main()
{
// freopen("bzoj1098.in","r",stdin);
memset(pre,0,sizeof(pre));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
for (int i=1;i<=n;i++) {l[i-1].next=i;l[i].pre=i-1;} l[n].next=0;
bfs();
sort(z+1,z+1+siz_z);
printf("%dn",siz_z);
if (siz_z>0) {for (int i=1;i<siz_z;i++) printf("%d ",z[i]);printf("%d",z[siz_z]); }
return 0;
}