题目概述

有 $n$ 个人和 $m$ 条关系 $(x,y)$ 表示 $x$ 和 $y$ 有联系方式。如果两个人没有联系方式就需要在同一个连通块，求出连通块个数和每个连通块点的个数。

解题报告

其实就是补图连通块个数，但是补图太tm大了，怎么办呢？因为原图只有 $m$ 条边，所以如果我们用链表把访问过的点删掉，就可以保证访问次数为 $O(n+m)$ ，因为如果原图有边就说明补图无法经过，所以只会无法经过 $O(m)$ 次。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=100000,maxm=4000000;

int n,m,l[maxn+5],r[maxn+5],que[maxn+5],ti,now[maxn+5];bool vis[maxn+5];
int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5];int ans[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
#define Delete(i) (l[r[i]]=l[i],r[l[i]]=r[i])
inline void Bfs(int s){
    int Head=0,Tail=0;que[++Tail]=s;Delete(s);vis[s]=true;ans[0]++;
    while (Head!=Tail){
        ans[ans[0]]++;int x=que[++Head];ti++;for (int j=lnk[x];j;j=nxt[j]) now[son[j]]=ti;
        for (int i=r[0];i<=n;i=r[i]) if (!vis[i]&&now[i]<ti) que[++Tail]=i,Delete(i),vis[i]=true;
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(m);for (int i=1;i<=n;i++) l[i]=i-1,r[i]=i+1;r[0]=1;l[n+1]=n;
    for (int i=1,x,y;i<=m;i++) readi(x),readi(y),Add(x,y),Add(y,x);
    for (int i=1;i<=n;i++) if (!vis[i]) Bfs(i);sort(ans+1,ans+1+ans[0]);
    printf("%d\n",ans[0]);for (int i=1;i<=ans[0];i++) printf("%d ",ans[i]);return 0;
}