这题就是坑人的，因为way我前一半存正图，后一半存反图，导致一般扩大两倍过不了，而是要扩大四倍，就是这个坑！！！！！
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=4e6+10; 7 struct node 8 { 9 int val; 10 int next; 11 }way[maxn]; 12 queue< int >q; 13 int n,m; 14 bool vis[1000100],cover[1000010]; 15 int nex[1000010]; 16 int cnt,head[100010]; 17 int last[1000010]; 18 int s[1000100],ans; 19 int tot=0; 20 int add(int x,int y) 21 { 22 way[++tot].next=head[x]; 23 way[tot].val=y; 24 head[x]=tot; 25 } 26 void de(int x) 27 { 28 nex[last[x]]=nex[x]; 29 last[nex[x]]=last[x]; 30 } 31 int main() 32 { 33 cin>>n>>m; 34 int x,y; 35 for(int i=1;i<=m;i++) 36 { 37 cin>>x>>y; 38 add(x,y); 39 add(y,x); 40 } 41 //cout<<tot<<endl; 42 nex[0]=1; 43 for(int i=1;i<n;i++) 44 { 45 last[i+1]=i; 46 nex[i]=i+1; 47 } 48 49 for(int i=1;i<=n;i++) 50 { 51 if(!vis[i]) 52 { 53 s[++ans]=1; 54 vis[i]=true; 55 q.push(i); 56 de(i); 57 // cout<<1111111<<endl; 58 while(!q.empty()) 59 { 60 int x=q.front(); 61 q.pop(); 62 for(int j=head[x];j;j=way[j].next) 63 { 64 if(!vis[way[j].val]) 65 { 66 cover[way[j].val]=true; 67 } 68 } 69 for(int j=nex[0];j;j=nex[j]) 70 { 71 if(!cover[j]) 72 { 73 vis[j]=true; 74 s[ans]++; 75 de(j); 76 q.push(j); 77 } 78 else 79 cover[j]=false; 80 } 81 } 82 } 83 } 84 //cout<<1111111<<endl; 85 sort(s+1,s+1+ans); 86 cout<<ans<<endl; 87 for(int i=1;i<=ans;i++) 88 { 89 cout<<s[i]<<" "; 90 } 91 /*cout<<endl<<endl; 92 for(int i=1;i<=n;i++) 93 { 94 cout<<nex[i]<<" "; 95 }*/ 96 return 0; 97 }