已完成今日补图连通块大学习

AC_Lover · 2026-01-30 16:32:32 · 算法·理论

大学习：CF920E

考虑暴力，直接 \mathrm{dfs}，遍历到 u 时在补图上寻找点 v，若其未被遍历过则遍历，这样可以搜出所有的补图连通块，分析一下时间复杂度，每次需要遍历找 v，而原图的边只有 O(n) 条，因此时间复杂度是 O(n^2)。考虑怎么优化，瓶颈在于找 v，考虑用并查集维护，实际是维护一个链表，这样可以 O(1) 跳到下一个需要搜的位置，时间复杂度为优化到了 O(n+m)。

#include <bits/stdc++.h>
#define psb push_back

using namespace std;

const int N=200005;
int n; unordered_map<int,bool> mp[N];
struct dsu
{
    int p[N],sz[N];
    void init() { for (int i=1;i<=n+1;i++) p[i]=i,sz[i]=1; }
    int find(int x) { return p[x]==x ? x : (p[x]=find(p[x])); }
    void merge(int x,int y) 
    {
        x=find(x), y=find(y);
        if (x^y) 
        {
            if (sz[x]<sz[y]) swap(x,y);
            p[y]=x, sz[x]+=sz[y];
        }

    }
} G, d;

bool vis[N];
void dfs(int u)
{
    vis[u]=true, G.p[u]=u+1;
    for (int v=G.find(1);v<=n;v=G.find(v+1))
        if (!mp[u].count(v))
            d.merge(u,v), dfs(v);
}

vector<int> ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int m;
    cin >> n >> m;
    while (m--) 
    {
        int x,y; cin >> x >> y;
        mp[x][y]=mp[y][x]=true;
    }
    G.init(), d.init(); 
    for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
    for (int i=1;i<=n;i++)
        if (d.find(i)==i)
            ans.psb(d.sz[i]);
    sort(ans.begin(),ans.end());
    cout << (int)ans.size() << "\n"; 
    for (int x : ans) cout << x << " "; cout << "\n";

    return 0;
}