P3452 [POI2007]BIU-Offices

ゞ浴缸里的玫瑰 2021-10-23 15:22 197阅读 0赞

[传送门][Link 1]

首先能想到 $n^2$ 的做法

枚举所有两点，看看是否有边相连，如果没有说明它们一定要在同一集合，用并查集维护一下就行

注意到如果没有边这个条件，其实就相当于问补图有边

所以题意可以转化为，求补图的每个联通块大小

求联通块可以想到 $bfs$，代码大概长这样：

while(!Q.empty())
    {
        int u=Q.front(); Q.pop(); tim++;
        for(int i=fir[u];i;i=from[i]) vis[to[i]]=tim;
        for(int i=1;i<=n;i++) if(vis[i]!=tim&&!inq[i]) Q.push(i);//inq[]维护点是否在队列中
    }

但是这样枚举点还是 $O(n^2)$ 的，发现对于已经在队列中的点，完全没有必要枚举到

所以维护一个链表，只存当前未访问过的点，每个点一访问到就删了，这样每个点只访问一次，每条边只访问两次

复杂度是线性的，然后就可过了

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<queue>
    using namespace std;
    typedef long long ll;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=2e5+7,M=4e6+7;
    int n,m,pre[N],nex[N],ans[N],tot,vis[N],tim;
    int fir[N],from[M],to[M],cntt;
    inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; }
    inline void del(int x) { pre[nex[x]]=pre[x]; nex[pre[x]]=nex[x]; }
    queue <int> Q;
    int main()
    {
        n=read(),m=read(); int a,b;
        for(int i=1;i<=m;i++)
        {
            a=read(),b=read();
            add(a,b); add(b,a);
        }
        for(int i=0;i<=n;i++) pre[nex[i]=i+1]=i;
        while(nex[0]!=n+1)
        {
            int x=nex[0],cnt=0;
            Q.push(x); del(x);
            while(!Q.empty())
            {
                int u=Q.front(); Q.pop(); cnt++; tim++;
                for(int i=fir[u];i;i=from[i]) vis[to[i]]=tim;
                for(int i=nex[0];i!=n+1;i=nex[i]) if(vis[i]!=tim) Q.push(i),del(i);
            }
            ans[++tot]=cnt;
        }
        sort(ans+1,ans+tot+1);
        printf("%d\n",tot);
        for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
        printf("\n");
        return 0;
    }

转载于:https://www.cnblogs.com/LLTYYC/p/11350513.html

[Link 1]: https://www.luogu.org/problem/P3452