办公楼biu
给出一张图，求出其补图所有联通块的个数及其大小。
黑暗爆炸OJ 1098
容易想到$O(n^2)$的算法：对于每一个点，枚举所有邻点打上标记，然后找那些没有被打上标记的点，将这些点加入到一个联通块中。
如果使用链表，可以将复杂度优化到$O(n + m)$，非常的神奇。
本来是非常的神秘，后来qko学长给我讲了下就变得非常神奇了 orz
链表优化后的总体思路与上类似，枚举每一个点，将邻点打上标记，接下来在链表中找那些没有被标记过的点加入到联通块中。这里我们维护链表中的元素为可能成为该点所在联通块的那些元素，这意味着对于那些已经加入其他联通块或是已经被加入到当前联通块的元素不会再被考虑。每次我们将那些元素加入到联通块中后，就将他们在链表中删去，这样就可以维护上述的性质。
初看总感觉会被卡到$O(n^2)$，因为某个点如果连了很多个邻边，那么在链表中就有可能会遍历到最后一个元素才只能删掉1个元素。那么会成为$O(n^2)$吗，应该是不会的。
按照我最开始粗浅的想法是，如果点数n和边数m同阶，那么不可能会有很多这种联通性极强的点，从而On的遍历链表的次数也不会很多。不过这样的解释终归有点牵强，问了qko学长后得知了一种更优美的说明方法：考察链表中每个点被遍历过的次数。根据补图的定义，某个点最多只会被冗余遍历$O(m_i)$次，$m_i$表示i节点的边的个数。因为如果有一条不连接该点的点正在进行扩散操作，那么该点因为不与其相连，一定会将其加入到补图联通块中，之后便会在链表中删去该节点的信息。只有那些与其原本相连的点在扩散过程中才会保留这些邻点不删去。那么总共访问链表的次数显然就是$O(m)$了。
另一方面，枚举每个点进行联通块扩散的时间为$O(n)$，所以总共时间复杂度为$O(n + m)$。
orz
太巧妙了
1const int maxn = 1e5 + 10, maxe = 2e6 + 10;
2int n, m;
3
4struct star{int to, next;};
5int head[maxn], top = 0;
6star edge[maxe << 1];
7void add(int u, int v){
8 edge[top].to = v;
9 edge[top].next = head[u];
10 head[u] = top++;
11}
12
13list<int> ls;
14queue<int> q;
15int vis[maxn];
16vector<int> ans;
17
18int main(){
19// Fastin;
20 clr(head, -1);
21 scanf("%d %d", &n, &m); for(int i = 0; i < m; i++){
22 int u, v; scanf("%d %d", &u, &v);
23 add(u, v); add(v, u);
24 }
25 for(int i = 1; i <= n; i++) ls.push_back(i);
26 while(!ls.empty()){
27 q.push(ls.front()); ls.pop_front();
28 int cnt = 0;
29 while(!q.empty()){
30 int now = q.front(); q.pop(); cnt++;
31 for(int i = head[now]; ~i; i = edge[i].next){
32 int to = edge[i].to;
33 vis[to] = 1;
34 }
35 list<int>::iterator it = ls.begin();
36 while(it != ls.end()){
37 if(vis[*it]){vis[*it] = 0; it++;}
38 else{q.push(*it); ls.erase(it++);}
39 }
40 }
41 ans.push_back(cnt);
42 }
43 int top = (int)ans.size();
44 printf("%d\n", top);
45 sort(ans.begin(), ans.end());
46 for(int i = 0; i < top; i++){
47 printf("%d", ans[i]);
48 printf(i != top - 1? " ": "\n");
49 }
50 return 0;
51}