BZOJ1098:[POI2007]办公楼biu 补图+链表+BFS

题目大意:

给定一个无向图,求出补图连通块的数目以及每一块的大小,按照从小到大的顺序输出.

思路:

首先由题意显然能够转化为上述问题.

在一个补图连通块中的所有节点必定在一个块中,由于要使得块数最多,不在同一补图连通块中的点显然也不能分到一起.

因此每一个补图连通块就是一个办公楼.

接下来考虑如何求.直接转化为补图是\(O(n^2)\)的.

我们考虑维护一个链表,每次寻找一个连通块时,首先选择链表中的一个元素删去并加入队列,找到链表中的与这个元素(在原图中)不相邻的所有元素,均在链表中删除并加入队列.直到队列为空我们就找到了一个连通块.

由于在链表中的每一个元素只会被删去一次,原图中的每一条边也只会被遍历一次,因此总的时间复杂度为\(O(n+m)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
#define M 2000010
int head[N],next[M<<1],end[M<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int l[N],r[N];
 
int ans[N],cnt;
 
int q[N],fr,ta;
 
int vis[N],tclock;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    int n,m;scanf("%d%d",&n,&m);
    int a,b;while(m--)scanf("%d%d",&a,&b),make(a,b);
 
    register int i,j;
    for(i=1;i<n;++i)l[i]=i-1,r[i]=i+1;
    l[0]=n,r[0]=1,l[n]=n-1,r[n]=0;
 
    while(r[0]){
        fr=ta=0;q[ta++]=r[0];l[r[r[0]]]=0,r[0]=r[r[0]];
        while(fr^ta){
            ++tclock;
            for(j=head[i=q[fr++]];j;j=next[j])vis[end[j]]=tclock;
            for(j=r[0];j;j=r[j])if(vis[j]!=tclock)q[ta++]=j,r[l[j]]=r[j],l[r[j]]=l[j];  
        }ans[++cnt]=ta;
    }
    sort(ans+1,ans+cnt+1);
    printf("%d\n",cnt);for(i=1;i<=cnt;++i)printf("%d ",ans[i]);
 
    return 0;
}