题解 P4833 【萨塔尼亚的一生之敌】

· · 题解

这题怎么就黑了（我这么菜怎么会做得出来黑题呢）

这题怎么做呢？其实主要是要细细读一下那两个性质

对于1，每个自己不同的领域的点之间都要有边

对于2，自己的领域的每一个点要和对面的每一个领域的每一个点要有边

认真看着两个条件是不是会发现如果对面拿了一个领域，那么这个领域作为自己的领域也是满足条件的

所以不要给走狗留领域

好了现在问题就是怎么分配这个领域了

显然对于两个联通块，若他们之间没有边，则要划分到同一个领域去

所以怎么划分领域？

对于每一个点A它必定属于一个领域，那么我们以这个点进行扩展，我们要这个领域尽量多，因此我们维护一个队列表示和当前枚举的A在不在一个领域内。对于这个A点沿着他的出边拓展，所有被A访问到的点都是允许不和A在同一个领域，所以偶没有被A访问到的点必定和A在同一个领域，这里我们就用一个桶来维护，每次将其++，把这些没有被访问到的点进入队列.然后我们要用一个limit维护这个领域大小，遍历这个桶，将遍历到的点如果他的桶的值小于limit，那么说明这个点不能被这个领域的所有点到达，因此他要属于这个领域，按照这个方法维护即可。具体细节见代码注释。

时间复杂度为O(m+nk),k为领域数量，m为边数

极端情况退化n^2?

不会的，因为此题m不大，因此可以知道k不会很大，这个时间复杂度能够通过此题。若有更优秀的做法欢迎指出。

（路过点个赞呀）

code：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

struct note{
    int seq,val,act;
}que[4000008];
int n,m,l,maxp;
int x[4000008],y[4000008],_last[4000008],_next[4000008];
int vis[4000008],cnt[4000008],fa[4000008],tp[4000006];

inline void edge(int u,int v){
    l++; x[l]=u; y[l]=v; _next[l]=_last[u]; _last[u]=l;
}
inline int _max(int a1,int a2){if (a1<a2) return a2; else return a1;}
bool cmp(int a1,int a2){return a1<a2;}

inline void dividing(int);

int main()
{
    scanf("%d%d",&n,&m);
    for (register int i=1;i<=n;i++) _last[i]=-1;
    for (register int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        edge(u,v),edge(v,u);
    }
    for (register int i=1;i<=n;i++)
        if (!vis[i]) dividing(i);
    printf("%d\n",maxp);
    sort(cnt+1,cnt+1+maxp,cmp);
    for (register int i=1;i<=maxp;i++) printf("%d ",cnt[i]);
}

inline void dividing(int pos)
{

    for (register int i=1;i<=n;i++) fa[i]=i,tp[i]=vis[i];
    register int limit=0,lef=1,rig=n,res=n,deep=n,spp=1;
    for (register int i=1;i<=n;i++) que[i].seq=i,que[i].val=0;//inti
    while (res && lef<=deep && deep<=10*n)
      if (que[lef].val<limit || spp)//若为第一个或者这个点的桶值没有到达limit
        {
            pos=que[lef].seq; lef++; 
            if (vis[pos]) continue; 
            vis[pos]=1;
            for (register int j=_last[pos];j!=-1;j=_next[j]){
                int tar=y[j];
                while (fa[tar]!=0 && fa[tar]!=tar) tar=fa[tar];
                que[tar].val++;
            }
            limit++;
            res--; spp=0;
        }else {
            if (que[lef].val==999999999) {lef++; continue;}
            rig++;
            fa[que[lef].seq]=rig;
            que[rig]=que[lef];
            que[lef].val=999999999;
            lef++;
            deep++;//遍历出边，更新最大deep（因为有下面的移动操作，不能到n就停
            //这个点到目前为止成立并不代表完全成立，要将他移动到队列末尾，fa数组维护他的新位置。
        }
    maxp++;
    for (register int i=1;i<=n;i++) 
        if (tp[i]!=vis[i]) cnt[maxp]++;//统计答案
}
}

（直接复制抄袭会ce) （bug不影响阅读） （这是重发的之前那个有一点bug）