题意很好理解，求给出图反图的联通块个数。
考虑这样一个事情：一个联通块里的点，最多只会被遍历一次，再遍历时没有任何意义
所以用链表来存，每遍历到一个点就将该点删掉
#include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<algorithm> using namespace std; #define N 100005 int e=1,head[N],n,m; int nxt[N],ans,pre[N],final[N],tot,q[N]; bool bo[N],flag[N]; struct edge{ int u,v,next; }ed[4000005]; void add(int u,int v) { ed[e].v=v; ed[e].next=head[u]; head[u]=e++; } void del(int x){ nxt[pre[x]]=nxt[x]; pre[nxt[x]]=pre[x]; } void bfs(int x) { int h=1,t=1; q[1]=x; while(h<=t){ int now=q[h++]; ans++; for(int i=nxt[0];i<=n;i=nxt[i]) bo[i]=0; for(int i=head[now];i;i=ed[i].next) bo[ed[i].v]=1; for(int i=nxt[0];i<=n;i=nxt[i]){ if(!bo[i]){ del(i); q[++t]=i; } } } } int main() { int u,v; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } nxt[0]=1; for(int i=1;i<=n+1;i++){ pre[i]=i-1; nxt[i]=i+1; } tot=0; for(int i=nxt[0];i<=n;i=nxt[0]){ ans=0; del(i); bfs(i); final[++tot]=ans; } sort(final+1,final+tot+1); printf("%d\n",tot); for(int i=1;i<=tot;i++) printf("%d ",final[i]); return 0; }