首先能想到 $n^2$ 的做法
枚举所有两点，看看是否有边相连，如果没有说明它们一定要在同一集合，用并查集维护一下就行
注意到如果没有边这个条件，其实就相当于问补图有边
所以题意可以转化为，求补图的每个联通块大小
求联通块可以想到 $bfs$，代码大概长这样：
while(!Q.empty()) { int u=Q.front(); Q.pop(); tim++; for(int i=fir[u];i;i=from[i]) vis[to[i]]=tim; for(int i=1;i<=n;i++) if(vis[i]!=tim&&!inq[i]) Q.push(i);//inq[]维护点是否在队列中 }
但是这样枚举点还是 $O(n^2)$ 的，发现对于已经在队列中的点，完全没有必要枚举到
所以维护一个链表，只存当前未访问过的点，每个点一访问到就删了，这样每个点只访问一次，每条边只访问两次
复杂度是线性的，然后就可过了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,M=4e6+7; int n,m,pre[N],nex[N],ans[N],tot,vis[N],tim; int fir[N],from[M],to[M],cntt; inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; } inline void del(int x) { pre[nex[x]]=pre[x]; nex[pre[x]]=nex[x]; } queue <int> Q; int main() { n=read(),m=read(); int a,b; for(int i=1;i<=m;i++) { a=read(),b=read(); add(a,b); add(b,a); } for(int i=0;i<=n;i++) pre[nex[i]=i+1]=i; while(nex[0]!=n+1) { int x=nex[0],cnt=0; Q.push(x); del(x); while(!Q.empty()) { int u=Q.front(); Q.pop(); cnt++; tim++; for(int i=fir[u];i;i=from[i]) vis[to[i]]=tim; for(int i=nex[0];i!=n+1;i=nex[i]) if(vis[i]!=tim) Q.push(i),del(i); } ans[++tot]=cnt; } sort(ans+1,ans+tot+1); printf("%d ",tot); for(int i=1;i<=tot;i++) printf("%d ",ans[i]); printf(" "); return 0; }