Codeforces 920E(BFS+链表优化)

Codeforces 920E
题意:给你一个无向图,求它补图的连通分量个数以及所有连通分量的大小,升序输出。

这题也就只能 BFS 暴力了,最开始将所有点放进一个数组,然后每次从里面拿一个出来 BFS 扩展,然后每一层扩展到的点实际上是不可达的,要把没有扩展到的点加进队列,并且在数组中删除。这样找出来就是一个联通分量了。但是数组要支持删除很慢,我们就用链表来做。

知识点:链表让数组支持$O(1)$删除,BFS取没有扩展的点加入队列的思想很好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 200000 + 5;
int n, m, l[MAXN], r[MAXN], vis[MAXN];
vector<int> G[MAXN], ans;
queue<int> q;
inline void ins(int x, int y) {G[x].push_back(y), G[y].push_back(x);}
inline void del(int x) {r[l[x]] = r[x], l[r[x]] = l[x];}
void bfs(int s) {
int sz = 0;
q.push(s), vis[s] = s;
while (!q.empty()) {
sz++;
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (vis[v] != u) vis[v] = u;
}
for (int i = r[0]; i != -1; i = r[i]) if (i != s && vis[i] != u) q.push(i), del(i);
}
ans.push_back(sz);
}
void clean() {
ms(vis, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y);
for (int i = 1; i <= n; i++) l[i] = i - 1, r[i - 1] = i;
l[0] = -1, r[n] = -1;
for (int i = r[0]; i != -1; i = r[i]) bfs(i), del(i);
sort(ans.begin(), ans.end());
printf("%d\n", (int)ans.size());
for (int i = 0; i < (int)ans.size(); i++) printf("%d ", ans[i]);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
------ 本文结束 ------