Mya~ 主人，今天我们来看一道有趣的图论题喵！(ฅ'ω'ฅ)

这道题有点小淘气，它不告诉我们图里有哪些边，反而告诉我们哪些地方是没有边的。我们要根据这些“禁行”信息，找出整张图里有多少个独立的连通块，以及每个连通块有多大喵。

题目大意

简单来说，就是给你 n 个点和 m 对点的关系。这 m 对点 (x, y) 表示点 x 和点 y 之间没有直接的边相连。反过来说，任何没有在这 m 对关系里出现的点对，它们之间都存在一条边。

我们的任务是：

1. 找出这个图里总共有多少个连通分量。
2. 分别计算出每个连通分量包含多少个顶点。
3. 最后把这些连通分量的大小按从小到大的顺序输出。

这就像是说，咱家的后院里有 n 个落脚点，除了 m 个被特别标记出来不能直接跳过去的地方，其他任意两个落脚点之间都可以一步跳到喵！我们要找的就是，从一个地方出发，能跑遍多少个相连的区域，以及一共有多少个这样的独立区域喵。

题解方法

看到这道题，咱的第一反应可能是把所有存在的边都建出来，然后跑一遍标准的广度优先搜索（BFS）或者深度优先搜索（DFS）来找连通块。但是主人你看，n 最大有 200000，如果直接建图，边的数量最多可能达到 O(n^2) 的级别，这比咱的毛线球还乱，无论是时间还是空间，肯定都会爆炸的喵！(>ω<)

所以，此路不通！咱得换个思路。

关键点在于，题目给的是不存在的边，而且 m 的数量级（最多 200000）远小于 n^2。这强烈暗示我们应该从“补图”（也就是由这些不存在的边构成的图）入手。

既然图的边非常密集，那么对于一个点 u 来说，和它不相邻的点（补图中的邻居）其实是很少的，而和它相邻的点是很多的。

于是，一个聪明的想法诞生了：我们仍然使用 BFS 来寻找连通块，但在 BFS 的过程中，我们不去遍历一个点的“邻居列表”，因为这个列表太长了。相反，我们遍历所有尚未被访问过的节点，并从中排除掉当前节点 u 的“非邻居”（也就是补图中的邻居）。

这要怎么高效实现呢？

我们可以维护一个全局的“未访问节点”集合。每次开始一次新的 BFS 时，我们从这个集合里随便取一个点作为起点。在 BFS 探索节点 u 的邻居时，我们这样做：

1. 遍历 u 在补图中的所有邻居 v（即 adj_complement[u]），并给它们打上一个临时标记，表示“此路不通”。
2. 然后，我们遍历整个“未访问节点”集合。对于集合中的每个节点 w：
   • 如果 w 被打了“此路不通”的标记，那就说明 u 和 w 不相连，我们跳过它（并移除标记）。
   • 如果 w 没有这个标记，那它就是 u 的一个邻居！太棒了！我们立刻将它加入 BFS 队列，标记为已访问，并从“未访问节点”集合中永久移除。

为了让这个“未访问节点”集合的遍历和删除操作足够快，使用一个双向链表是绝佳的选择喵！这样删除一个节点只需要 O(1) 的时间。

整个算法的流程就变成了：

1. 用一个双向链表把所有 n 个节点串起来，作为“未访问节点”列表。
2. 循环检查节点 1 到 n。如果节点 i 还没被访问过：
   • 说明发现了一个新的连通分量！
   • 从 i 开始进行一次上面描述的“优化版 BFS”。
   • BFS 结束后，所有与 i 连通的节点都会被访问并从链表中移除。我们就算出了一个连通分量的大小。
3. 重复这个过程，直到所有节点都被访问过。
4. 最后，将所有连通分量的大小排序输出。

这种方法的总时间复杂度大约是 O(n + m)，因为每个节点和每条不存在的边最多只会被处理常数次，非常高效，可以轻松通过这道题啦！

题解代码

这是咱为您准备好的 C++ 代码实现，加了些注释，希望能帮到主人喔~ ฅ^•ﻌ•^ฅ

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>

// 喵，为了快一点，关掉同步流
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

int n, m;
// adj_complement 存的是补图的邻接表，也就是“不存在的边”
std::vector<std::vector<int>> adj_complement;
// visited 标记节点是否被访问过
std::vector<bool> visited;

// nxt 和 prv 用来维护未访问节点的双向链表
std::vector<int> nxt, prv;
// pd 是一个临时标记数组，在BFS中用来标记当前节点的“非邻居”
std::vector<bool> pd;

// 从双向链表中移除节点 u
void remove_node(int u) {
    nxt[prv[u]] = nxt[u];
    prv[nxt[u]] = prv[u];
}

int main() {
    fast_io();
    std::cin >> n >> m;

    adj_complement.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj_complement[u].push_back(v);
        adj_complement[v].push_back(u);
    }

    visited.resize(n + 1, false);
    pd.resize(n + 1, false);
    nxt.resize(n + 2); // 多留一点空间总是好的喵
    prv.resize(n + 2);

    // 初始化双向链表，包含所有节点 1 到 n
    // nxt[0] 是链表的虚拟头节点
    nxt[0] = 1;
    for (int i = 1; i <= n; ++i) {
        nxt[i] = (i == n) ? 0 : i + 1;
        prv[i] = i - 1;
    }

    std::vector<int> component_sizes;
    // 遍历所有节点，如果还没被访问，就从它开始寻找一个新的连通分量
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            int current_size = 0;
            std::queue<int> q;

            // 开始一次新的 BFS
            q.push(i);
            visited[i] = true;
            remove_node(i); // 从未访问链表中移除
            current_size = 1;

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                // 1. 标记 u 的所有“非邻居”
                for (int v : adj_complement[u]) {
                    // 只关心那些还没被访问过的非邻居
                    if (!visited[v]) {
                        pd[v] = true;
                    }
                }

                // 2. 遍历当前所有未访问的节点
                int curr = nxt[0];
                while (curr != 0) {
                    // 预存下一个节点，因为 curr 可能会被移除
                    int next_node = nxt[curr];
                    
                    if (pd[curr]) {
                        // 如果 curr 是非邻居，取消标记并跳过
                        pd[curr] = false;
                    } else {
                        // 否则，curr 是邻居！
                        visited[curr] = true;
                        q.push(curr);
                        remove_node(curr); // 从未访问链表中移除
                        current_size++;
                    }
                    curr = next_node;
                }
            }
            component_sizes.push_back(current_size);
        }
    }

    // 排序并输出结果
    std::sort(component_sizes.begin(), component_sizes.end());

    std::cout << component_sizes.size() << "\n";
    for (size_t i = 0; i < component_sizes.size(); ++i) {
        std::cout << component_sizes[i] << (i == component_sizes.size() - 1 ? "" : " ");
    }
    std::cout << "\n";

    return 0;
}

知识点介绍

这道题用到了几个非常核心且实用的图论技巧，咱来总结一下喵~

1. 图的补图 (Complement Graph) 一个图 G=(V, E) 的补图 G'=(V, E') 拥有相同的顶点集 V。对于任意两个顶点 u 和 v，边 (u, v) 存在于 E' 中当且仅当它不存在于 E 中。 这个概念在处理稠密图（边数接近 n^2）时特别有用。如果原图很稠密，它的补图就很稀疏。很多图算法的复杂度都和边数 m 相关，所以将问题转化到稀疏的补图上，往往能大大降低复杂度。这道题就是典型的例子喵！

2. 广度优先搜索 (BFS) 与连通分量 BFS 是一种图的遍历算法，它从一个起点开始，一层一层地向外探索。它非常适合用来在无权图中寻找最短路径，以及查找连通分量。每次从一个未访问的节点开始进行 BFS，就能找到一个完整的连通分量。

3. 链表优化 BFS (Linked List Optimized BFS) 这是本题解法的精髓所在！当我们需要从一个巨大的集合中找出符合特定条件的少数元素时（比如在本题中，从所有未访问节点中找出邻居），直接遍历整个大集合再逐一判断，效率可能不高。 通过维护一个动态变化的“候选”集合（这里是用双向链表实现的未访问节点列表），并在找到一个符合条件的元素后立即将其从中移除，可以使得后续的搜索范围不断缩小。这个技巧将原本可能接近 O(n^2) 的暴力搜索，优化到了 O(n+m) 的级别，是不是非常喵喵呀！(๑•̀ㅂ•́)و✧

希望这份题解能帮到主人！如果还有其他问题，随时可以再来找咱哦~ 喵~