CF1477D Nezzar and Hidden Permutations 解题报告

解题报告

CF1477D Nezzar and Hidden Permutations解题报告：

更好的阅读体验

题意

给定一个无向图，将它定向为一个 DAG，求出两个拓扑序让两个拓扑序相同的结点数最少。

$1\leqslant n,m\leqslant 5\times 10^5$。

分析

埋藏在任务计划的陈年老题。/tuu

首先观察样例，发现很多点都可以拓扑序不相同，我们考虑先求出固定点，然后让其他的结点巧妙地安排顺序使得两个拓扑序不同。

我们发现我们可以每次找到一个与所有点都有连边的点，然后把它删掉，重复这个过程，就可以获得所有固定点，我们钦定它们全部放在最开始的拓扑序。

然后会剩下 $n'$ 个度数不超过 $n'-2$ 的点，这个性质难以利用，考虑补集转换，那么它的补图每个点度数一定大于 $1$。

那么我们考虑对每个连通块求出一个 dfs 树，对每棵树进行菊花剖分，然后对于每个菊花都可以安排两种顺序：先中心再四周，先四周再中心，不难发现这样每个点的两个拓扑序一定不相同。

如何进行菊花剖分呢？（我们只需要大小大于 $1$ 的菊花）我们可以对于每个点 $x$ 分类讨论：如果它附近有没有划分的点那么直接把 $x$ 和这些点划分成一个菊花。否则如果 $x$ 与某一个中心相邻，则将 $x$ 划分入这个菊花。（注意这里必须判断，原因是菊花剖分的过程中中心可能移动，具体见下方）如果还是不行，考虑与 $x$ 相邻的这个菊花，如果大小大于 $2$，$x$ 可以直接拿走一个点；否则可以移动这个菊花的中心到另一个点上，并将 $x$ 放入。

我们发现这样一定会让每个点不重不漏地划分入若干个菊花，时间复杂度 $O((n+m)\log n)$。

代码

坑点：

• 多组数据要清空。
• 不要讨巧少讨论情况。
• 注意要把结点和颜色分开的明明白白。
• 在求固定点的时候一定要用当前固定的点数量来判断能否变为固定点。

#include<stdio.h>
#include<set>
#include<vector> 
#include<queue>
#include<map>
using namespace std;
const int maxn=500005;
int T,n,m,tot,cols;
int ans1[maxn],ans2[maxn],deg[maxn],col[maxn],cen[maxn],size[maxn];
vector<int>v[maxn],t[maxn];
set<int>s;
queue<int>q;
map<pair<int,int>,int>mp;
void dfs1(int x,int last){
    for(set<int>::iterator it=s.begin();it!=s.end();it++)
        if(mp.find(make_pair(*it,x))==mp.end())
            t[x].push_back(*it),t[*it].push_back(x);
    for(int i=0;i<t[x].size();i++)
        if(t[x][i]!=last)
            s.erase(t[x][i]);
    for(int i=0;i<t[x].size();i++)
        if(t[x][i]!=last)
            dfs1(t[x][i],x);
}
void dfs2(int x,int last){
    if(col[x]==0){
        int flg=0;
        for(int i=0;i<t[x].size();i++)
            if(col[t[x][i]]==0)
                flg=1;
        if(flg){
            col[x]=++cols,cen[cols]=x,size[cols]=1;
            for(int i=0;i<t[x].size();i++)
                if(col[t[x][i]]==0)
                    col[t[x][i]]=cols,size[cols]++;
        }
        else{
            if(cen[col[t[x][0]]]==t[x][0])
                col[x]=col[t[x][0]],size[col[t[x][0]]]++;
            else if(size[col[t[x][0]]]==2)
                col[x]=col[t[x][0]],cen[col[t[x][0]]]=t[x][0],size[col[t[x][0]]]++;
            else col[x]=++cols,cen[cols]=x,size[cols]=2,size[col[t[x][0]]]--,col[t[x][0]]=cols;
        }
    }
    for(int i=0;i<t[x].size();i++)
        if(t[x][i]!=last)
            dfs2(t[x][i],x);
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            s.insert(i);
        for(int i=1;i<=m;i++){
            int x,y;;
            scanf("%d%d",&x,&y);
            v[x].push_back(y),v[y].push_back(x),deg[x]++,deg[y]++;
            mp[make_pair(x,y)]=mp[make_pair(y,x)]=1;
        }
        for(int i=1;i<=n;i++)
            if(deg[i]==n-1)
                s.erase(i),q.push(i);
        while(!q.empty()){
            int x=q.front();
            printf("x=%d\n",x);
            q.pop(),ans1[x]=ans2[x]=++tot;
            for(int i=0;i<v[x].size();i++){//travel all nodes
                int y=v[x][i];
                deg[y]--;
                if(s.find(y)!=s.end()&&deg[y]>=n-tot-1)
                    s.erase(y),q.push(y);
            }
        }
        for(int i=1;i<=n;i++)
            if(s.find(i)!=s.end())
                s.erase(i),dfs1(i,0);
        for(int i=1;i<=n;i++)
            if(col[i]==0&&ans1[i]==0)
                dfs2(i,0);
        for(int i=1;i<=cols;i++){
            ans1[cen[i]]=++tot;
            for(int j=0;j<t[cen[i]].size();j++){
                int k=t[cen[i]][j];
                if(col[k]==i)
                    ans2[k]=tot,ans1[k]=++tot;
            }
            ans2[cen[i]]=tot;
        }
        for(int i=1;i<=n;i++)
            printf("%d%c",ans1[i],i==n? '\n':' ');
        for(int i=1;i<=n;i++)
            printf("%d%c",ans2[i],i==n? '\n':' ');
        tot=cols=0,mp.clear();
        for(int i=1;i<=n;i++)
            deg[i]=col[i]=ans1[i]=0,v[i].clear(),t[i].clear();
    }
    return 0;
}