题目理解

我们需要将 $n$ 个雇员分配到尽可能多的办公楼中，使得不同办公楼之间的任意两个雇员都互相留有电话。

换句话说，如果两个雇员在不同的办公楼，那么他们必须在原图中有边相连。

关键转化

这个问题等价于在补图中求连通分量：

• 原图：雇员之间有电话关系
• 补图：雇员之间没有电话关系
• 条件转化：不同办公楼的雇员在原图中必须有边 ↔ 同一办公楼的雇员在补图中不能有边

因此，问题转化为：在补图中找出所有连通分量，每个连通分量就是一个办公楼。

算法思路

核心思想

使用 BFS 遍历补图的连通分量。由于补图可能非常稠密（$n$ 最大 $10^5$，直接存储补图不可行），我们采用数据结构优化的方法。

数据结构优化技巧

• 维护一个集合 st 存储所有尚未访问的节点
• 在 BFS 过程中，对于当前节点 u，我们只考虑与 u 在原图中没有边的未访问节点
• 使用标记数组 col 来辅助判断

代码详细解析

数据结构定义

vector<int> edge[N];  // 原图的邻接表
set<int> st;          // 未访问节点集合
vector<int> ans;      // 存储每个办公楼的大小
bool vis[N];          // 标记节点是否被访问
int col[N];           // 临时标记数组

BFS 遍历补图连通分量

void bfs(int u) {
    queue<int> q;
    q.push(u);
    st.erase(u);      // 从未访问集合中删除
    vis[u] = 1;       // 标记为已访问
    res++;            // 当前连通分量大小计数

    while (!q.empty()) {
        int nw = q.front();
        q.pop();
        
        // 标记所有与原图中相邻的未访问节点
        for (auto v : edge[nw]) {
            if (!vis[v])
                col[v] = 1;  // 标记为"不能直接访问"
        }

        auto it = st.begin();
        while (it != st.end()) {
            int v = *it;
            it++;

            if (!col[v]) {
                // 在补图中有边：可以访问
                vis[v] = 1;
                st.erase(v);  // 从未访问集合中删除
                q.push(v);
                res++;
                continue;
            } else {
                col[v] = 0;   // 重置标记
            }
        }
    }
}

算法流程

1. 初始化：将所有节点加入未访问集合 st
2. 遍历节点：对于每个未访问节点，启动 BFS
3. BFS过程：
   • 标记当前节点的所有原图邻居
   • 遍历未访问集合，选择未被标记的节点（即在补图中相连）
   • 将这些节点加入队列并继续 BFS
4. 记录结果：记录每个连通分量的大小

复杂度分析

时间复杂度

• 每个节点只会被访问一次
• 每条边也只会被考虑一次
• 总体复杂度：$O((n+m)\log n)$，主要来自 set 操作

空间复杂度

• $O(n+m)$：存储图和辅助数组

样例分析

对于样例输入：

7 16
(16条边)

算法执行过程：

1. 发现补图的连通分量
2. 找到 3 个连通分量，大小分别为 1, 2, 4
3. 输出结果：3 和 1 2 4

算法正确性证明

为什么这样能找到补图连通分量？

• 在 BFS 中，我们只遍历那些在补图中有边的节点
• 通过 col 数组排除原图中有边的节点
• st 集合确保每个节点只被访问一次

为什么这是最优解？

• 补图的每个连通分量内部在补图中连通，在原图中是独立集
• 不同连通分量之间的节点在原图中必有边（否则会在同一连通分量）
• 因此每个连通分量可以作为一个办公楼，且这是最大可能的划分

总结

本题的关键在于：

1. 问题转化：将办公楼分配问题转化为补图连通分量问题
2. 数据结构优化：使用集合来高效遍历补图，避免显式构建补图
3. BFS技巧：通过标记原图邻居来间接处理补图边

这种"补图+BFS+数据结构优化"的思路是处理稠密图连通性问题的经典方法。