翻车笔记_ [POI2007]办公楼biu [图论, bfs, 清奇脑回路]

qwq 从另一个方向考虑会有新的想法

懵逼的 题目

qwq

扯淡的 题解

如果…我…不二分的话…我是不是可以把没有联系方式的人之间连边…然后…难道就是…连通块的个数?

复杂度是不是炸了

如果我稍微…优化一下…

…1h passed

无果, 遂翻题解…链表优化$bfs$…Emmmmmmm? 这是个啥玩意…

仔细想了一下…Emmmmmmm! 我们只要保证一个点只会被遍历一遍不就行了qwq

那么, 我们用一个链表, 存下所有的点, 代表还未遍历过的点

每次:

  • 从链表头取出一个元素, 把他删掉, 加到队列里
  • 开始$bfs$, 每次从队首取出一个元素. 遍历链表, 如果链表中当前的元素与当前节点没有边相连, 就把这个点从链表中删除, 并加入队列, 当前联通块的大小$+1$

这样就保证了所有的点只会被遍历一次, 是不是很妙?

至于怎么确定一个点是否和当前点有边相连, 直接用set<int>[]会$TLE$…所以我们可以搞一个vis[], 记录与当前点相连的点即可

沙茶的 代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**************************************************************
Problem: 1098
User: Cansult
Language: C++
Result: Accepted
Time:8760 ms
Memory:52372 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstring>
#include <algorithm>
#include <set>
#include <list>
#include <queue>
#include <vector>
#define MAXN (100000 + 5)
#define MAXM (2000000 + 5)
using namespace std;
struct edg
{
int from, to, next;
}b[MAXM << 1];
vector<int> ans;
set<int> edg[MAXN];
int n, m, g[MAXN], cntb;
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from, b[cntb].to = to;
g[from] = cntb;
}
void bfs()
{
list<int> sh;
bool vis[MAXN];
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++)
sh.push_back(i);
while (!sh.empty())
{
int s = *sh.begin();
sh.pop_front();
queue<int> q;
q.push(s);
int cnt = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
vis[b[i].to] = true;
for (list<int>::iterator i = sh.begin(), j; i != sh.end();)
if (!vis[*i])
{
q.push(*i);
++cnt;
j = i;
++i;
sh.erase(j);
}
else
++i;
for (int i = g[dq]; i; i = b[i].next)
vis[b[i].to] = false;
}
ans.push_back(cnt);
}
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++)
printf("%d ", ans[i]);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1, srx, sry; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
bfs();
return 0;
}

By 沙茶 Cansult