洛谷P3452 [POI2007]BIU-Offices 题解

题目链接：P3452 [POI2007]BIU-Offices

题意：

Bytel 是一家移动通信公司。该公司的每位员工都收到了一部公司生产的电话，电话的通讯录中存储着一些同事的电话号码（每部手机中也都有该手机本身的电话号码）。

由于业务扩张，公司总部需要迁移至新的办公区。为了提高工作效率，董事会决定在不同栋楼工作的每一对员工需要相互知道对方的电话号码。即如果 \(u\) 和 \(v\) 在不同的楼工作，则 \(u\) 的通讯录里需要存储 \(v\) 的电话号，\(v\) 的通讯录里也要存储 \(u\) 的电话号码。

同时，董事会决定租用尽可能多的楼，以确保良好的工作条件。现在你需要帮助 Bytel 公司计算出他们需要租用多少栋楼。

输入格式：

输入第一行包含两个整数 \(n,m\)，分别代表公司的员工数和通讯录的信息数，员工从 \(1\) 到 \(n\) 编号。

接下来 \(m\) 行，每行两个整数 \(a_i,b_i\)，表示 \(a_i\) 和 \(b_i\) 相互知道对方的电话号码，保证任意两条信息不重复。

输出格式：

输出第一行包含一个整数 \(t\)：董事会需要租用多少栋办公楼。

第二行包含 \(t\) 个整数，第 \(i\) 个整数 \(c_i\) 表示在第 \(i\) 栋建筑工作的员工数量。你的输出需要保证 \(c_i\) 是单调不下降的。

如果有多种合法方案，你可以输出任意一种。

数据范围：

\(2 \leq n \leq 10^5\)，\(1 \leq m \leq 2 \times 10^6\)，\(1 \leq a_i \lt b_i \leq n\)。

直接按原题建边，边 \((u,v)\) 的意义就是 \(u,v\) 不在同一个楼里面（在同一个楼里肯定不会更优）

这个东西就很反人类，于是考虑建 \(G\) 的反图 \(G^{\prime}\) 。

此时边的意义就转化为： \(u,v\) 在同一个楼里面

那问题就转化为了求 \(G^{\prime}\) 的连通块个数

但是我们不能直接用 \(\mathtt{bfs}\) ，因为边数是 \(O(n^2)\) 的（因为 \(G\) 是稀疏图，所以 \(G^{\prime}\) 是稠密图）

不难发现，此时的连通块数量一定不会很多

因此在拓展一个连通分量的时候，无需再考虑已经在连通分量里的点。

这个东西可以用并查集维护。

具体地， f[x] 表示的是编号大于 \(x\) 的点中第一个未被访问的点

有点像那个线性区间推平的题目 -> 洛谷P2391 白雪皑皑 题解

因为 \(G^{\prime}\) 是稠密图，所以时间复杂度为期望 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))
#define M ((int)(2e6+15))

int n,m,pos=1,cur,tim,val[N],f[N],used[N],head[N];
struct Edge{int u,v,next;}e[M*2];
void addEdge(int u,int v) {e[++pos]={u,v,head[u]}; head[u]=pos;}
void init(int n){for(int i=1; i<=n; i++) f[i]=i;}
int find(int x){return f[x] == x ? x : f[x] = find(f[x]);}
queue<int> q;
void bfs(int st)
{
    q.push(st); val[++cur]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop(); ++tim; f[u]=find(u+1);
        // 时间戳优化频繁清空
        for(int i=head[u]; i; i=e[i].next) used[e[i].v]=tim;
        for(int i=find(1); i<=n; i=find(++i))
            if(used[i] != tim) // 可以访问
                ++val[cur], f[i]=find(i+1), q.push(i);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    init(n+1);
    for(int i=1; i<=n; i = find(++i)) bfs(i);
    cout << cur << '\n';
    sort(val+1,val+1+cur);
    for(int i=1; i<=cur; i++) cout << val[i] << " \n"[i==cur];
    return 0;
}