思路题+链表--bzoj1098: [POI2007]办公楼biu

本文主要是介绍思路题+链表--bzoj1098: [POI2007]办公楼biu，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
本质上是求补图的每个联通块大小
考虑$bfs$，枚举每个未访问的点作为起点，然后将与他连边的点都标记一下放到一个栈里，然后将他删除，在栈里的点也是这么做的，这样就可以处理出这个联通块大小，可以用链表维护

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 100005
#define M 2000005
using namespace std;
int n,m,cnt,head[N],to[M<<1],nxt[M<<1];
int l[N],r[N],stk[N],top,vis[N],siz[N],tot;inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f; 
}inline void add(int x,int y){to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}inline void del(int now){l[r[now]]=l[now],r[l[now]]=r[now];
} int main(){n=rd(); m=rd();for(int i=1;i<=m;i++){int a=rd(),b=rd();add(a,b);}for(int i=1;i<=n;i++)l[i]=i-1,r[i]=i+1;int cur=1;while(cur<=n){siz[++tot]=1;for(int i=head[cur];i;i=nxt[i]) vis[to[i]]=cur;del(cur); int now=r[0];while(now<=n){if(vis[now]!=cur) stk[++top]=now,siz[tot]++,del(now);now=r[now];}while(top){int u=stk[top--];for(int i=head[u];i;i=nxt[i]) vis[to[i]]=u;now=r[0];while(now<=n){if(vis[now]!=u) stk[++top]=now,siz[tot]++,del(now);now=r[now];}}cur=r[0];}printf("%d\n",tot);sort(siz+1,siz+tot+1);for(int i=1;i<=tot;i++)printf("%d ",siz[i]);return 0;
}

这篇关于思路题+链表--bzoj1098: [POI2007]办公楼biu的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---