bzoj 1098 poi2007 办公楼 bfs+链表

本文主要是介绍bzoj 1098 poi2007 办公楼 bfs+链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意很好理解，求给出图反图的联通块个数。

考虑这样一个事情：一个联通块里的点，最多只会被遍历一次，再遍历时没有任何意义

所以用链表来存，每遍历到一个点就将该点删掉

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define N 100005
int e=1,head[N],n,m;
int nxt[N],ans,pre[N],final[N],tot,q[N];
bool bo[N],flag[N];
struct edge{int u,v,next;
}ed[4000005];
void add(int u,int v)
{ed[e].v=v;ed[e].next=head[u];head[u]=e++;
}
void del(int x){nxt[pre[x]]=nxt[x];pre[nxt[x]]=pre[x];
}
void bfs(int x)
{int h=1,t=1;q[1]=x;while(h<=t){int now=q[h++]; ans++;for(int i=nxt[0];i<=n;i=nxt[i]) bo[i]=0;for(int i=head[now];i;i=ed[i].next)bo[ed[i].v]=1;for(int i=nxt[0];i<=n;i=nxt[i]){if(!bo[i]){del(i); q[++t]=i;}}}
}
int main()
{int u,v;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);add(u,v); add(v,u);}nxt[0]=1;for(int i=1;i<=n+1;i++){pre[i]=i-1;nxt[i]=i+1;}tot=0;for(int i=nxt[0];i<=n;i=nxt[0]){ans=0;del(i); bfs(i);final[++tot]=ans;}sort(final+1,final+tot+1);printf("%d\n",tot);for(int i=1;i<=tot;i++)printf("%d ",final[i]);return 0;
}

这篇关于bzoj 1098 poi2007 办公楼 bfs+链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---