新姿势：链表存图快速删除
显然两个没有直接相连的点要放到同一个集合里
但是直接搞一个图的补图会挂掉
考虑用链表维护点序列
每次bfs删除一个点和与其没有直接相连的点
复杂度大概。。。能过
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; int read(){ char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9') x=x*10+c-48,c=getchar(); return x; } #define N 100005 #define M 4000005 int n,m,pr[N],nx[N],ans,pos[N]; bool is[N]; int Cnt,hd[N],nxt[M],ed[N],poi[M]; void adde(int x,int y){ nxt[ed[x]]=++Cnt; hd[x]=hd[x]?hd[x]:Cnt; ed[x]=Cnt; poi[Cnt]=y; } void del(int x){nx[pr[x]]=nx[x]; pr[nx[x]]=pr[x];} #define to poi[i] void bfs(int S){ queue <int> h; h.push(S); while(!h.empty()){ int x=h.front(); h.pop(); ++pos[ans]; for(int i=hd[x];i;i=nxt[i]) is[to]=1; for(int i=nx[0];i<=n;i=nx[i]) if(!is[i]) del(i),h.push(i); for(int i=hd[x];i;i=nxt[i]) is[to]=0; } } int main(){ n=read(); m=read(); for(int i=0;i<=n+1;++i) pr[i]=i-1,nx[i]=i+1; for(int i=1,u,v;i<=m;++i) u=read(),v=read(),adde(u,v),adde(v,u); for(int i=nx[0];i<=n;i=nx[0]) ++ans,del(i),bfs(i); sort(pos+1,pos+ans+1); printf("%d ",ans); for(int i=1;i<=ans;++i) printf("%d ",pos[i]); return 0; }