图论、广度优先搜索

给定一个有 $n$ 个节点的无向完全图，在里面去掉 $m$ 条边，求连通分量个数和每个连通分量的大小。

经典套路，维护和点 $i$ 不连边的所有节点，遍历图到点 $u$ 时枚举所有未被访问过的节点 $v$，如果两个节点有连边则将 $v$ 入队并标记为已访问。全部 $n$ 个点入队之前至多有 $2m$ 次查询的结果为未连边。

需要一个支持快速删除元素和遍历所有元素的数据结构，可以使用哈希表在期望 $O(n)$ 的时间复杂度内完成，但实际上时间复杂度 $O(n \log n)$ 的并查集跑得更快。

由于 $n,m$ 同阶，总体时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
set<int> s[200'005];
int n,m,f[200'005];
int ask(int x){return x==f[x] ? x:f[x]=ask(f[x]);}
int bfs(int S){
    int ret=1;
    f[S]=ask(S-1);
    queue<int> q;
    for(q.push(S);!q.empty();q.pop()){
        int now=q.front();
        for(int i=ask(n);i>=1;i=ask(i-1)){
            if(s[now].count(i)) continue;
            f[i]=ask(i-1);
            ++ret,q.push(i);
        }
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y;
        s[x].emplace(y);
        s[y].emplace(x);
    }
    iota(f+1,f+n+1,1);
    vector<int> ans;
    for(int i=1;i<=n;i++) if(ask(i)==i) ans.push_back(bfs(i));
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<'\n';
    for(int i:ans) cout<<i<<' ';
    return 0;
}