1098: [POI2007]办公楼biu
Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 2021 Solved: 1026
[Submit][Status][Discuss]
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

求补图的联通块个数。

存图的时候用vector，set会TLE。

然后再vector上二分。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,cnt,vis[N],res[N],del[N],q[N];
set<int> st;	vector<int> g[N];
void bfs(int x){
	res[cnt]++; st.erase(x); vis[x]=1; int r=0,L=1,R=0; q[++R]=x;
	while(L<=R){
		int u=q[L++]; vis[u]=1;
		for(set<int>::iterator i=st.begin();i!=st.end();i++){
			if(*lower_bound(g[u].begin(),g[u].end(),*i)!=*i){
				q[++R]=*i; res[cnt]++; del[++r]=*i;
			}
		}
		while(r)	st.erase(del[r--]);
	}
}
signed main(){
	scanf("%d %d",&n,&m);
	for(int i=1,a,b;i<=m;i++)	
		scanf("%d %d",&a,&b),g[a].push_back(b),g[b].push_back(a);
	for(int i=1;i<=n;i++)	st.insert(i),sort(g[i].begin(),g[i].end());
	for(int i=1;i<=n;i++)	if(!vis[i])	cnt++,bfs(i);
	sort(res+1,res+1+cnt);
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++)	printf("%d ",res[i]);puts("");
	return 0;
}