BZOJ1098:[POI2007]办公楼biu 补图+链表+BFS
题目大意:
给定一个无向图,求出补图连通块的数目以及每一块的大小,按照从小到大的顺序输出.
思路:
首先由题意显然能够转化为上述问题.
在一个补图连通块中的所有节点必定在一个块中,由于要使得块数最多,不在同一补图连通块中的点显然也不能分到一起.
因此每一个补图连通块就是一个办公楼.
接下来考虑如何求.直接转化为补图是O(n2)的.
我们考虑维护一个链表,每次寻找一个连通块时,首先选择链表中的一个元素删去并加入队列,找到链表中的与这个元素(在原图中)不相邻的所有元素,均在链表中删除并加入队列.直到队列为空我们就找到了一个连通块.
由于在链表中的每一个元素只会被删去一次,原图中的每一条边也只会被遍历一次,因此总的时间复杂度为O(n+m).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include<cstdio>#include<cstring>#include<cctype>#include<climits>#include<iostream>#include<algorithm>using namespace std; #define N 100010#define M 2000010int 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;} |
评论 (0)