思路:
补图bfs,将未访问的点存进set里
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=2e5+5; bool vis[N]; int head[N]; int a[N]; int cnt=0,ans=0; struct edge{ int to,next; }edge[N*2]; inline add_edge(int u,int v){ edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } inline bfs(int n){ set<int>s; set<int>st; queue<int>q; for(int i=1;i<=n;i++){ s.insert(i); } for(int i=1;i<=n;i++){ if(!vis[i]){ s.erase(i),q.push(i),vis[i]=true,a[++ans]++; while(!q.empty()){ int u=q.front(); q.pop(); for(int j=head[u];~j;j=edge[j].next){ int v=edge[j].to; if(s.count(v)==0)continue; s.erase(v); st.insert(v); } for(set<int>::iterator it=s.begin();it!=s.end();it++){ if(!vis[*it])q.push(*it),vis[*it]=true; a[ans]++; } s.swap(st); st.clear(); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,u,v; mem(head,-1); cin>>n>>m; for(int i=0;i<m;i++){ cin>>u>>v; add_edge(u,v); add_edge(v,u); } bfs(n); sort(a+1,a+1+ans); cout<<ans<<endl; for(int i=1;i<=ans;i++)cout<<a[i]<<' '; cout<<endl; return 0; }