首页 > 代码库 > [BZOJ1098][POI2007]办公楼biu

[BZOJ1098][POI2007]办公楼biu

[BZOJ1098][POI2007]办公楼biu

试题描述

FGD开办了一家电话公司。他雇用了N个职员,给了每个职员一部手机。每个职员的手机里都存储有一些同事的电话号码。由于FGD的公司规模不断扩大,旧的办公楼已经显得十分狭窄,FGD决定将公司迁至一些新的办公楼。FGD希望职员被安置在尽量多的办公楼当中,这样对于每个职员来说都会有一个相对更好的工作环境。但是,为了联系方便起见,如果两个职员被安置在两个不同的办公楼之内,他们必须拥有彼此的电话号码。

输入

第一行包含两个整数N(2<=N<=100000)和M(1<=M<=2000000)。职员被依次编号为1,2,……,N.以下M行,每行包含两个正数A和B(1<=A<b<=n),表示职员a和b拥有彼此的电话号码)

输出

包含两行。第一行包含一个数S,表示FGD最多可以将职员安置进的办公楼数。第二行包含S个从小到大排列的数,每个数后面接一个空格,表示每个办公楼里安排的职员数。

输入示例

7 16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7

输出示例

3
1 2 4

数据规模及约定

见“输入

题解

显然如果能够建立原图的反图,那么一个连通块的所有点放在同一个办公楼就好了。但是点数太多,导致反图的边数巨大而无法存储。

于是可以使用 BFS + 链表优化,就是你每次扩展的时候把原图中连出的点打上标记,然后暴力看一下链表中还剩哪些点,然后往那些点转移就好了,转移到的点直接从链表删除,因为我们无须重复考虑同一个点。

看上去这个应该很快,然而我并不会严格证明复杂度。。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
	return x * f;
}

#define maxn 100010
#define maxm 4000010

int n, m, head[maxn], nxt[maxm], to[maxm], Pre[maxn], Nxt[maxn];

void AddEdge(int a, int b) {
	to[++m] = b; nxt[m] = head[a]; head[a] = m;
	swap(a, b);
	to[++m] = b; nxt[m] = head[a]; head[a] = m;
	return ;
}

bool vis[maxn], tag[maxn];
int Q[maxn], hd, tl, ans, tot[maxn];
void del(int u) {
	int lp = Pre[u], ln = Nxt[u];
	Nxt[lp] = ln; Pre[ln] = lp; vis[u] = 1;
	return ;
}
void bfs(int s) {
	hd = tl = 0; Q[++tl] = s;
	del(s); tot[ans] = 1;
	while(hd < tl) {
		int u = Q[++hd];
		for(int e = head[u]; e; e = nxt[e]) tag[to[e]] = 1;
		for(int i = Nxt[0]; i; i = Nxt[i]) if(!tag[i]) del(i), tot[ans]++, Q[++tl] = i;
		for(int e = head[u]; e; e = nxt[e]) tag[to[e]] = 0;
	}
	return ;
}

int main() {
	n = read(); int m = read();
	for(int i = 1; i <= m; i++) {
		int a = read(), b = read();
		AddEdge(a, b);
	}
	for(int i = 0; i < n; i++) Nxt[i] = i + 1, Pre[i+1] = i;
	
	for(int i = 1; i <= n; i++) if(!vis[i]) ans++, bfs(i);
	
	sort(tot + 1, tot + ans + 1);
	printf("%d\n", ans);
	for(int i = 1; i <= ans; i++) printf("%d ", tot[i]);
	
	return 0;
}

 

[BZOJ1098][POI2007]办公楼biu