[文章目录]
Description
FGD开办了一家电话公司。他雇用了N个职员，给了每个职员一部手机。每个职员的手机里都存储有一些同事的电话号码。由于FGD的公司规模不断扩大，旧的办公楼已经显得十分狭窄，FGD决定将公司迁至一些新的办公楼。FGD希望职员被安置在尽量多的办公楼当中，这样对于每个职员来说都会有一个相对更好的工作环境。但是，为了联系方便起见，如果两个职员被安置在两个不同的办公楼之内，他们必须拥有彼此的电话号码。N（2<=N<=100000）和M（1<=M<=2000000）
不就是求一个补图的联通块个数吗？？？
等等？？？咋求啊？？？啊啊啊啊啊啊啊。
看完题解好像是什么链表优化bfs的东西。
考虑bfs的时候我们的时间耗在每次找那些不具有边的点上，然而实际上有很多这样的点已经被扫过了。没有必要重新扫。（没连的边很多，连的边很少）
维护一个双向链表存所有没有确定联通块的点，每次扫一遍链表，将没有标记的点剔除。考虑每次扫的过程，没有标记的点直接删除了，标记的点被多余扫到的次数为边数级别。时间复杂度O(n+m)
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,tot,ans;
queue<int>q;
vector<int>v[100100];
int num[100100],tim[100100];
int nxt[100100],pre[100100];
inline void del(int x)
{
nxt[pre[x]]=nxt[x];
pre[nxt[x]]=pre[x];
}
int main()
{
scanf("%d%d",&n,&m); int x,y;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
v[x].push_back(y); v[y].push_back(x);
}
nxt[0]=1;
for(int i=1;i<=n;++i)
nxt[i]=i+1, pre[i]=i-1;
pre[n+1]=n;
while(nxt[0]!=n+1)
{
q.push(nxt[0]); del(nxt[0]); int x; ans++;
while(!q.empty())
{
x=q.front(); q.pop(); num[ans]++; tot++;
for(int i=0;i!=v[x].size();++i) tim[v[x][i]]=tot;
for(int i=nxt[0];i!=n+1;i=nxt[i])
if(tim[i]!=tot) q.push(i),del(i);
}
}
sort(num+1,num+ans+1);
printf("%d\n",ans);
for(int i=1;i<=ans;++i) printf("%d ",num[i]);
return 0;
}