题意很好理解，求给出图反图的联通块个数。
考虑这样一个事情：一个联通块里的点，最多只会被遍历一次，再遍历时没有任何意义
所以用链表来存，每遍历到一个点就将该点删掉
#include#include #include #include #include using namespace std;#define N 100005int 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;}