1 // 补图连通块 bfs + 链表优化 2 #include <cstdio> 3 #include <queue> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7  8 struct Edge { 9     int to, nxt;10 };11 12 struct Node {13     int pre, nxt;14 };15 16 const int maxm = 2000000 + 5;17 const int maxn = 100000 + 5;18 19 int n, m, cnt;20 int head[maxn], vis[maxn], vi[maxn];21 Edge e[maxm << 1];22 Node l[maxn];23 vector<int> ans;24 25 void add_edge(int u, int v) {26     e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;27     e[++cnt].to = u; e[cnt].nxt = head[v]; head[v] = cnt;28 }29 30 void del_node(int p) {31     l[l[p].pre].nxt = l[p].nxt;32     l[l[p].nxt].pre = l[p].pre;33 }34 35 void bfs() {36     queue<int> q; // 维护当前补图连通块中要扩展的节点37     while (l[0].nxt != 0) { // 当前链表不为空，说明还有节点未属于任何连通块38         int p = l[0].nxt; // 枚举链表中存在的一个节点，成为一个新的连通块中的第一个节点39         del_node(p); // 从链表中删除此节点40         q.push(p); // 节点入队41         int sum = 1; // 当前连通块数量为142         while (!q.empty()) { // 不断对属于当前连通块中的节点求其补图连通节点从链表中删除并加入队列43             p = q.front(); q.pop(); // 弹出连通块中的一个节点44             for (int i = head[p]; i; i = e[i].nxt) // 枚举此节点的边并标记45                 vis[e[i].to] = 1;46             for (int i = l[0].nxt; i; i = l[i].nxt) // 查找当前还未属于任何连通块的节点，如果未被标记则属于p的补图连通节点，此连通块的节点数目自增，并将联通节点加入队列然后从链表中删除47                 if (!vis[i]) { sum++; q.push(i); del_node(i); }48             for (int i = head[p]; i; i = e[i].nxt) vis[e[i].to] = 0; // 恢复标记,被标记的节点可能为当前块中（队列中的）需要扩展的节点的补图连通节点49         }50         ans.push_back(sum); // 将完整的连通块中的节点数目保存在数组中51     }52 }53 54 int main() {55     scanf("%d%d", &n, &m);56     for (int i = 1, u, v; i <= m; i++) { // 建图57         scanf("%d%d", &u, &v);58         add_edge(u, v);59     }60     for (int i = 1; i <= n; i++) { // 将节点1 ~ N初始化为一个链表（维护未在任何连通块中的节点），l[0].nxt指向当前链表中的表头节点， 链表为空的条件是l[0].nxt = 061         l[i].pre = i - 1;62         l[i].nxt = i + 1;63     } l[0].nxt = 1; l[n].nxt = 0;64     bfs(); // bfs求补图连通块65     printf("%d\n", ans.size()); // 输出连通块数目66     sort(ans.begin(), ans.end()); // 将各个连通块数目按升序排序67     for (int i = 0; i < ans.size(); i++) // 升序输出各连通块数目68         printf("%d ", ans[i]);69     return 0;70 }