BZOJ1098 [POI2007]办公楼biu

题面在这里

​

直接用set维护没有遍历的点

BFS时遍历整个set，找下是否在没有边的集合中

两边的贡献都只有\(\log\)，所以总的是\(O(n\log n+m\log m)\)

​

示例程序：

#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

const int maxn=100005;
int n,e,ans[maxn];
set<int> S;
set<int>::iterator it;
vector<int> V[maxn];
int que[maxn],del[maxn];
void BFS(){
	int hed=0,til=1;
	que[1]=*S.begin();S.erase(S.begin());
	while (hed!=til){
		int x=que[++hed]; del[0]=0;
		for (it=S.begin();it!=S.end();it++)
		 if ((*lower_bound(V[x].begin(),V[x].end(),*it))!=(*it)){
		 	que[++til]=*it;del[++del[0]]=*it;
		 }
		while (del[0]) S.erase(del[del[0]--]);
	}
	ans[++ans[0]]=til;
}
int main(){
	scanf("%d%d",&n,&e);
	for (int i=1,x,y;i<=e;i++)
	 scanf("%d%d",&x,&y),V[x].push_back(y),V[y].push_back(x);
	for (int i=1;i<=n;i++)
	 S.insert(i),sort(V[i].begin(),V[i].end());
	while (!S.empty()) BFS();
	sort(ans+1,ans+1+ans[0]);
	printf("%d\n",ans[0]);
	for (int i=1;i<=ans[0];i++) printf("%d ",ans[i]);
	return 0;
}