https://oj.neu.edu.cn/problem/1387
给一个点数N <= 100000, 边 <= 1000000的无向图，求补图的联通块数，以及每个块包含的点数
由于点数太大，补图会是稠密图，甚至建立补图都要O（n^2），只能挖掘一下联通块，bfs，补图的性质，从原图入手求补图的联通块：
在原图中不直接相邻的点，在补图中一定属于同一个联通块
每个点只属于一个联通块，所以找好一个联通块之后可以删去这个联通块的所有点，把图规模缩小
这样子：1.准备一个集合放所有未探索的点，初始化时将1～N放进去
2.从集合中取一点放入队列（新的联通块）
3.当队列不为空时，从队列中取一个点u并弹出，将原图中与u直接相连的点标记；遍历集合，将在集合中的（即未探索的）并且未被标记的点（这些点属于本联通块）入队并从集合中删去，将标记删去。重复执行直到队列为空
4.集合不为空转2，为空结束
考虑有删除操作和时间问题，集合的实现当然是选择链表，用数组实现的双向链表即可
优化有两个：一是通过原图找补图的联通块；二是把搜过的点删除，这样每次找未标记的点时比起从1循环到N更优（常数优化（误））
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 1e5+, maxm = 1e6+, inf = 0x3f3f3f3f;
struct lnk{
int val;
int pre, nxt;
}lk[maxn];
struct edge{
int v, nxt;
}e[maxm*];
int head[maxn], tot, block_cnt, n, m;
int adj[maxn], vis[maxn], num[maxn];
void addedge(int u, int v){
e[tot] = (edge){v, head[u]};
head[u] = tot++;
}
void dele(int x){
lk[lk[x].nxt].pre = lk[x].pre;
lk[lk[x].pre].nxt = lk[x].nxt;
}
void src(){
for(int i = ; i <= n; i++){
vis[i] = adj[i] = ;
}
queue<int>Q;
block_cnt = ;
while(lk[].nxt != -){
//puts("blk++");
Q.push(lk[].nxt);
//printf("take %d\n", lk[0].nxt);
vis[lk[lk[].nxt].val] = ;
dele(lk[].nxt);
block_cnt++;
num[block_cnt] = ;
while(!Q.empty()){
int x = Q.front();
x = lk[x].val;
//printf("%d\n", x);
Q.pop();
for(int i = head[x]; ~i; i = e[i].nxt){
int v = e[i].v;
adj[v] = ;
}
for(int i = lk[].nxt; ~i; i = lk[i].nxt){
int w = lk[i].val;
if(!vis[w] && !adj[w]){
Q.push(w);
vis[w] = ;
dele(i);
num[block_cnt]++;
}
}
for(int i = head[x]; ~i; i = e[i].nxt){
int v = e[i].v;
adj[v] = ;
}
}
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++)
head[i] = -;
tot = ;
while(m--){
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
for(int i = ; i <= n; i++){
lk[i].val = i;
lk[i].pre = i-;
lk[i].nxt = i+;
}
lk[n].nxt = -;
lk[].nxt = ;
src();
sort(num+, num+block_cnt+);
printf("%d\n", block_cnt);
for(int i = ; i <= block_cnt; i++){
printf("%d%c", num[i], i == block_cnt ? '\n' : ' ');
}
}
return ;
}
/*
3
5 7
1 2
1 3
1 4
1 5
2 3
2 4
2 5
6 9
1 4 1 5 1 6
2 4 2 5 2 6
3 4 3 5 3 6
3 3
1 2 2 3 3 1 */