luogu P3452 [POI2007]BIU-Offices

本文主要是介绍luogu P3452 [POI2007]BIU-Offices，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

两种写法，主要是复杂度的证明上比较有趣
1. 并查集+BFS
对于每个点，最多只会进入队列一次，这部分的复杂度是O(n)
每个点最多会在 for (int i = find(1); i <= n; i = find(i + 1))这段话中被访问 \(edge[i].size() + 1\) 次，因为如果某个点和它没有边，这个点就会和后面的合并，再也不会在这个循环中被访问到，而和它有边的点只有 edge[i].size() 个，所以在edge[i].size() + 1 次时一定可以把它合并，因此 \(\Sigma{edge[i].size()}=m\)，这部分最多被访问 \(O(m)\) 次，因此总的复杂度为 \(O(n + m)\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector < int > edge[N];
int ans[N], f[N], n, m, cnt, vis[N];
int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
void BFS(int x) {
	queue < int > q;
	q.push(x); f[x] = x + 1;
	ans[++cnt] = 1;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto v:edge[u])
			vis[v] = u;
		for (int i = find(1); i <= n; i = find(i + 1))
			if (vis[i] != u)
				q.push(i), ans[cnt]++;
	}     
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int a, b;
			scanf("%d%d", &a, &b);
			edge[a].push_back(b);
			edge[b].push_back(a);
		}
	for (int i = 1; i <= n + 1; i++)	f[i] = i;
	for (int i = 1; i <= n; i++)
		if (f[i] == i)
			BFS(i);
	printf("%d\n", cnt);
	sort(ans + 1, ans + cnt + 1);
	for (int i = 1; i <= cnt; i++)
		printf("%d ", ans[i]);
	return 0;
}

2. 链表+队列
   大概的想法和上面差不多，唯一的区别就是把删除的过程变成了并查集的合并变成了链表的删除。

这篇关于luogu P3452 [POI2007]BIU-Offices的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！