P3452 [POI2007]办公室

**这题妙啊** 题意：给定一张无向图，将n个点分成若干个集合，使得任意分属两个集合的点对之间 都有边直接相连。求最多分成的集合数量以及每个集合中的点数 一开始想直接枚举点暴力，发现数据范围1e5，放弃了 想到bfs却又没什么具体实现方法 看到题解才想到链表和bfs结合的思路 ~~实在是妙啊~~ 显然，对于一个已知起点，与它没有边相连的点一定和它属于同一集合 根据这一点，就可以从不同的点分别进行bfs 在bfs中如果直接从1枚举到n，显然复杂度不可接受 这就用到了链表：每一个点入队时，将其从链表中删去，保证下一次不再访问到，加快 了枚举的速度，避免了最后一个点TLE的尴尬 ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<algorithm> #define reg register using namespace std; const int N=1e5+5,M=2e6+5; struct node { int to,nxt; }edge[M<<1]; int n,m,num,cnt,head[N],ans,res[N],nxt[N],pre[N]; bool vis[N],exist[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num]=(node){to,head[from]}; head[from]=num; } inline void del(int k) { nxt[pre[k]]=nxt[k]; pre[nxt[k]]=pre[k]; } inline void bfs(int k) { queue<int>q; q.push(k); vis[k]=1; del(k); cnt=1; while (!q.empty()) { int u=q.front(); q.pop(); memset(exist,0,sizeof(exist)); for (reg int i=head[u];i;i=edge[i].nxt) exist[edge[i].to]=1; for (reg int i=nxt[0];i<=n;i=nxt[i]) if (!exist[i]) q.push(i),vis[i]=1,++cnt,del(i); } res[++ans]=cnt; } int main() { n=read(),m=read(); for (reg int i=1;i<=m;i++) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } for (reg int i=1;i<=n;i++) pre[i]=i-1,nxt[i]=i+1; for (reg int i=1;i<=n;i++) if (!vis[i]) bfs(i); printf("%d\n",ans); sort(res+1,res+ans+1); for (reg int i=1;i<=ans;i++) printf("%d ",res[i]); return 0; } ```