P3452 [POI2007] BIU-Offices

Fzrcy · 2023-11-24 22:03:25 · 题解

简要题意：给你一个无向图 (V,E)，将点集划分为若干个子集，使得对于任意的两个点 x,y，且 x 和 y 不在同一个集合中，满足 x 和 y 有连边，求点集最多可以划分为多少个子集，及其方案。

先对无向图的边集 E 取反得到 E'，显然在 E' 中有连边的两个点必须在同一个集合中，所以答案为反图的连通块数和所有连通块的大小。

我们用一个链表维护未删去的点的集合，初始为 \{1,2,\dots,n\}，进行以下操作直到链表为空。

• 从链表中选出任意一个点 s 加入拓展队列，并从链表中删去，并进行以下操作：
• 1. 从拓展队列中选出一个点 x，并删去。
• 2. 将所有与 x 相连的点标记。
• 3. 暴力遍历链表将未标记的点加入拓展队列并从链表中删去，然后将有标记的点的标记删去。
• 则反图中 s 所在的连通块的大小为点加入拓展队列的次数。

因为操作 2 的时间复杂度为 O(m)、操作 3 的时间复杂度为 O(n+m)（最多只有 m 次是只枚举且不从链表中删去）。

所有总时间复杂度为 O(n+m)。

// qwq
#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+6;
int Vis[N],ans,A[N],ban[N];
int n,m,pr[N],nxt[N];
vector<int>e[N];
queue<int> q;
void D(int x){
    nxt[pr[x]]=nxt[x];
    pr[nxt[x]]=pr[x];
}
int main(){
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++)
        cin>>x>>y,e[x].push_back(y),
        e[y].push_back(x);
    for(int i=1;i<n;i++)
        pr[i+1]=i,nxt[i]=i+1;
    nxt[0]=1;
    for(int i=1;i<=n;i++)if(!Vis[i]){
        A[++ans]=1,q.push(i),Vis[i]=1,D(i);
        while(!q.empty()){
            int u=q.front();q.pop();Vis[u]=1;
            for(int v:e[u])ban[v]=1;
            for(int j=nxt[0];j;j=nxt[j])
                if(!ban[j])D(j),Vis[j]=1,++A[ans],q.push(j);
                else ban[j]=0;
        }
    }
    sort(A+1,A+ans+1);
    cout<<ans<<'\n';
    for(int i=1;i<=ans;i++)
        cout<<A[i]<<' ';
    return 0;
}