例题 P3452
链表+bfs 链表主要是优化 减少循环次数 #include<bits/stdc++.h> using namespace std; inline int rd(){ int x=0,k=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar();} return k*x; } const int N=4000010; typedef long long ll; struct node{ int to,ne; }a[N]; int n,m,num,h[100010],e[100010],sum[100010],pre[100010],nxt[100010],tmp[100010]; int ans; inline void add(int x,int y){ a[++num]=(node){ y,h[x]}; h[x]=num; } inline void del(int x){ e[x]=1; nxt[pre[x]]=nxt[x]; pre[nxt[x]]=pre[x]; } int main() { n=rd(); m=rd(); int x,y; for(int i=1;i<=m;++i){ x=rd(); y=rd(); add(x,y); add(y,x); } for(int i=1;i<=n;++i) pre[i]=i-1,nxt[i]=i+1; nxt[n]=0; nxt[0]=1; queue<int >q; for(int i=1;i<=n;++i) if(!e[i]){ del(i); ans++; q.push(i); while(!q.empty()){ x=q.front(); q.pop(); for(int j=h[x];j;j=a[j].ne) tmp[a[j].to]=1; for(int j=nxt[0];j;j=nxt[j]) if(!tmp[j]&&!e[j]){ //或者直接if(!tmp[j]) q.push(j); sum[ans]++; del(j); } for(int j=h[x];j;j=a[j].ne) tmp[a[j].to]=0; } } sort(sum+1,sum+ans+1); printf("%d\n",ans); for(int i=1;i<=ans;i++)printf("%d ",sum[i]+1); return 0; }