【传送门：BZOJ1098】
简要题意：
给出n个人与m个关系，每个关系包括x,y两个数，表示x与y能够相互联系对方。现在要将这n个人分成k块，使得不同块的任意两个人之间能够互相联系，求出最大的k
题解：
本来以为直接就补图+tarjan过掉，结果发现补图边数是n2级别的，稳T
然后发现其实很多状态是不用多次询问的，点最多问一次，边也最多问一次
直接上链表保存当前不在一个联通块里的人，然后BFS合并
对于一个x，先将它从链表中删除，然后将它的所有能联系的人都从链表中删除，存到一个临时链表中，然后原链表中剩下的数一定与x在一个联通块里（因为他们都不能与x联系），然后将这些剩下的数插入队列，将临时链表代替链表就行了
第一次做复杂链表的题。。
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<queue> using namespace std; struct node { int x,y,next; }a[4100000];int len,last[110000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int nxt[110000],lst[110000],r1,r2; void del(int x) { if(lst[x]!=0) nxt[lst[x]]=nxt[x]; if(nxt[x]!=0) lst[nxt[x]]=lst[x]; if(nxt[r1]==x) nxt[r1]=nxt[x]; } int ans[110000],cnt,sum; bool v[110000]; queue<int> q; void bfs() { v[nxt[r1]]=false; q.push(nxt[r1]); nxt[r1]=nxt[nxt[r1]]; while(q.empty()==0) { int x=q.front();q.pop(); sum++; ans[cnt]++; nxt[r2]=0; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false) continue; del(y); if(nxt[r2]!=0) { nxt[y]=nxt[r2]; lst[nxt[r2]]=y; lst[y]=0; } else nxt[y]=0; nxt[r2]=y; } for(int i=nxt[r1];i;i=nxt[i]) { v[i]=false; q.push(i); } nxt[r1]=nxt[r2]; } } int main() { int n,m; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } memset(nxt,0,sizeof(nxt));memset(lst,0,sizeof(lst)); for(int i=2;i<=n;i++) nxt[i-1]=i,lst[i]=i-1; memset(v,true,sizeof(v)); cnt=0; r1=n+1,r2=n+2; nxt[r1]=1; memset(v,true,sizeof(v)); sum=0; while(1) { cnt++;bfs(); if(sum==n) break; } printf("%d ",cnt); sort(ans+1,ans+cnt+1); for(int i=1;i<cnt;i++) printf("%d ",ans[i]); printf("%d ",ans[cnt]); return 0; }