【bzoj1098】办公楼
题意
FGD开办了一家电话公司。他雇用了N个职员,给了每个职员一部手机。每个职员的手机里都存储有一些同事的电话号码。由于FGD的公司规模不断扩大,旧的办公楼已经显得十分狭窄,FGD决定将公司迁至一些新的办公楼。FGD希望职员被安置在尽量多的办公楼当中,这样对于每个职员来说都会有一个相对更好的工作环境。但是,为了联系方便起见,如果两个职员被安置在两个不同的办公楼之内,他们必须拥有彼此的电话号码。
\(2<=N<=100000,1<=M<=2000000\)
分析
要求块内任意,块外充满连边的最小划分数。
那就等价于补图上块内任意,块外无连边的最小划分数。
那么就等价于求补图的联通块个数。
对\(n=100000\)的稠密图来讲,
直接求联通块会炸。
所以要利用到\(M\leq 2000000\)的特性。
我最初的想法是:我们可以枚举任意一对的\((i,j)\),若它们在原图中不存在连边,那么用并查集把它们合并。
由于这是一幅稠密图,所以\((i,j)\)有很大的概率存在连边,所以我们对于每个点\(i\),不需要枚举所有的\(j\),只需要随机枚举\(T\)个,然后尝试连边即可。
然而WA了......
接下来说的是正解。
求连通块的方法常有搜索或者并查集。
并查集看似不行,我们考虑搜索的过程,并根据\(M\leq 2000000\)的特性优化。
BFS:对于一个点\(i\),找与它连通的所有点\(j\),再找与\(j\)连通的所有点\(k\)......
把所有找到的点删去,ans++。
普通的实现上,最大的瓶颈在于已经删除的点我们还反复枚举了......
那么我们就不反复枚举好了,直接使用双向链表来删点,复杂度就优化到了\(O(n)\),因为最多有\(2M\)次失败。
还看到一种更精彩的代替双向链表的做法。
就是直接使用并查集代替双向链表。
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
const int N=131072;
int n,m;
vector<int> g[N];
int vis[N],f[N];
int cnt[N],len;
int hsn[N],q[N],qh,qt;
int rd(void) {
int x=0,f=1; char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
int Find(int x) {
if (f[x]==x) return x;
return f[x]=Find(f[x]);
}
void Erase(int st) {
qh=qt=0; q[++qt]=st; vis[st]=1;
cnt[len]++;
f[st]=Find(st+1);
while (qh!=qt) {
int x=q[++qh];
rep(i,1,g[x].size()) {
int nx=g[x][i-1];
hsn[nx]=1;
}
int nx=Find(1);
while (nx!=n+1) {
if (!hsn[nx]) {
q[++qt]=nx; vis[nx]=1; cnt[len]++;
f[nx]=Find(nx+1);
}
nx=Find(nx+1);
}
rep(i,1,g[x].size()) {
int nx=g[x][i-1];
hsn[nx]=0;
}
}
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("sd.in","r",stdin);
freopen("sd.out","w",stdout);
#endif
n=rd(),m=rd();
rep(i,1,m) {
int x=rd(),y=rd();
g[x].push_back(y),g[y].push_back(x);
}
rep(i,1,n+1) f[i]=i;
rep(i,1,n) if (!vis[i]) {
len++;
Erase(i);
}
sort(cnt+1,cnt+len+1);
printf("%d\n",len);
rep(i,1,len)
printf("%d ",cnt[i]);
printf("\n");
return 0;
}
小结
(1)并查集可以代替双向链表,且实现更容易。
(2)外界充满边=补图外界无边,注意充满边的转化方法,最大团也是充满边的一种体现形式。
(3)连通块个数的统计,通常使用并查集或者搜索实现。