Luogu

分析

考虑到如果两个点之间没有边，那么这两个点一定会分在一个集合里。也就是说我们要求的实际上是补图的连通块。

但是直接连边去求边数是 $n^2-m$ 级别的，显然存不下。

考虑一个很暴力的想法：每次找一个还没有找连通块的点，然后 BFS 找连通块。具体就是扩展 $u$ 时，先标记 $u$ 的所有出点，然后所有没有找到连通块的没有被标记的点都和 $u$ 在一个连通块中。

问题就是怎么维护还没有找连通块的点。这个可以维护一个链表，或者拿一个 vector 存。

具体实现及细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=2000000+10;

int n,m;

struct edge { int v,nxt; } e[M<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int pre[N],nxt[N];
inline void del(int x) { pre[nxt[x]]=pre[x],nxt[pre[x]]=nxt[x]; }

int ans=0,sz[N],vis[N];
inline void solve(int s) {
    queue<int> Q; del(s),Q.push(s),sz[++ans]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=head[u];i;i=e[i].nxt) vis[e[i].v]=1;
        for (re int i=nxt[0];i<=n;i=nxt[i])
            if (!vis[i]) del(i),Q.push(i),++sz[ans];
        for (re int i=head[u];i;i=e[i].nxt) vis[e[i].v]=0;
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    for (re int i=1;i<=n+1;++i) pre[i]=i-1;
    for (re int i=0;i<=n;++i) nxt[i]=i+1;
    for (re int i=nxt[0];i<=n;i=nxt[0]) solve(i);
    printf("%d\n",ans);
    sort(sz+1,sz+ans+1);
    for (re int i=1;i<=ans;++i) printf("%d ",sz[i]); puts("");
    return 0;
}
最后修改：2019 年 10 月 16 日 10 : 18 PM
© 允许规范转载