题解：P11832 [省选联考 2025] 图排列

P_Bisector · 2025-03-15 13:21:19 · 题解

废话

大佬都太巨了！怎么都会广义串并联图！我在冬令营的时候听到双极定向就没往下继续听了，于是这里就有了一篇双极定向题解。食用价值疑似不大。

Part 1 赛时想法（森林）

以下内容可以获得 44pts 的好成绩。加上暴力的 8pts 可以稳进非强省省队。

首先我们观察题意可得，我们相当于把这个图拍到一个数轴上成为 P9901 中所定义的“弯曲半平面直线同向图”的无向版本。而我们所需要求的则是点拍到数轴上以后最小的字典序。

考虑树的情况，首先无脑将最小的放在最前面，接下来可以发现标号最小的点的所有儿子的子树必将连续。那么我们在树上 DP 找到每个子树字典树最小时第一个数的最小值（定义为 g_x），接下来对子树按 g_x 从小到大排序，依次选择这些子树向下 dfs 即可。如果某个节点上 x<g_x ，那么就先 dfs g_u<x 的 u 再将 x 计入答案。

树做出来之后，森林就是平凡的。每一个连通块在 dfs 结束后就可以看做一条长长的链，将链上的点依次计入答案。当链上某个点的标号小于其他链的第一个点的标号就将这个链插入它前面。

赛时代码（不带注释）：

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,c;
const int N=100050;
vector<int>rt,g[N],ans[N],Ans;
int vis[N],f[N],pos;
void dfs(int x){
    vis[x]=1;f[x]=x;
    for(int i=0;i<g[x].size();i++)
        if(vis[g[x][i]]==0)
            dfs(g[x][i]),f[x]=min(f[x],f[g[x][i]]);
}
void dfs2(int x,int q){
    vis[x]=1;
    int flag=0;
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(vis[v])continue;
        if(f[v]>x){
            if(flag==0){
                flag=1;
                ans[q].push_back(x);
            }
            dfs2(v,q);
        }else{
            dfs2(v,q);
        }
    }
    if(flag==0){
        flag=1;
        ans[q].push_back(x);
    }
}
void purslane(int x){
    for(int i=0;i<ans[x].size();i++){
        while(pos!=rt.size()&&ans[x][i]>rt[pos]){
            pos++;
            purslane(pos-1);
        }
        Ans.push_back(ans[x][i]);
    }
}
bool cmp(int a,int b){
    return f[a]<f[b];
}
void solve(){
    scanf("%d%d",&n,&m);
    rt.clear();pos=0;
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }/*
    for(int i=1;i<=n;i++)
        sort(g[i].begin(),g[i].end());

    for(int i=1;i<=n;i++)vis[i]=0;
    while(pos<rt.size())pos++,Dfs(rt[pos-1]);
    printf("\n");
    for(int i=1;i<=n;i++)g[i].clear();*/
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            rt.push_back(i);
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++){
        vis[i]=0;
    }
    for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end(),cmp);
    for(int i=0;i<rt.size();i++){
        dfs2(rt[i],i);
    }
    while(pos<rt.size())pos++,purslane(pos-1);//check
    for(int i=0;i<Ans.size();i++){
        printf("%d ",Ans[i]);
    }
    printf("\n");
    for(int i=1;i<=n;i++)g[i].clear();
    for(int i=0;i<rt.size();i++)ans[i].clear();
    Ans.clear();
    for(int i=1;i<=n;i++){
        vis[i]=0;
    }
}
int bfa[20],bfb[20],bfc[20];
struct seg{
    int l,r;
}s[30];
void bfcheck(){
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            int Q=bfc[s[i].l],R=bfc[s[i].r];
            int S=bfc[s[j].l],T=bfc[s[j].r];
            if(Q>R)swap(Q,R);if(S>T)swap(S,T);
            if(Q<S&&S<R&&R<T||S<Q&&Q<T&&T<R){
                return;
            }
        }
    }
    for(int i=1;i<=n;i++)Ans.push_back(bfa[i]);
}
void bfdfs(int x){
    if(x==n+1){
        bfcheck();
    }
    if(x==1){
        bfb[1]=1;
        bfa[1]=1;
        bfdfs(x+1);
        return;
    }
    for(int i=1;i<=n;i++){
        if(Ans.size())return;
        if(bfb[i]==0){
            bfb[i]=1;
            bfa[x]=i;
            bfc[i]=x;
            bfdfs(x+1);
            bfb[i]=0;
        }
    }
}
void bf(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&s[i].l,&s[i].r);
    bfdfs(1);
    for(int i=0;i<Ans.size();i++){
        printf("%d ",Ans[i]);
    }
    printf("\n");
    Ans.clear();
}
int main(){
    freopen("graperm.in","r",stdin);
    freopen("graperm.out","w",stdout);
    int T;
    scanf("%d%d",&c,&T);
    while(T--){
        if(c>2)solve();
        else bf();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

Part 2 whk课上思路（仙人掌以及一些性质）

（课上摸鱼证据）

首先我们可以注意到，如果树变成了仙人掌，那么我们可以建一棵圆方树（具体实现时因为某些原因写的是广义圆方树），而这棵圆方树中方点的 g_x 的计算方式就变成了两端的 g 的最小值。这看似没什么用。但是我们如果仔细分析这张图的性质可以发现它的每一个点双都有且仅有一个哈密顿回路！于是问题转化成了如何找到这条哈密顿回路。

Part 3 补题过程思路（正解）

为方便思考，把哈密顿回路称作环，摆在最外面，并将其他所有边放在里面。

注意到对于点双中的任何一条边，其要么将整个哈密顿回路切开成为左右两部分（易证这当中不存在边连接左右两部分），要么是环上的边（这种情况视作切割成环和空集两部分）。因此以这条边的两端为双极（s 和 t）进行双极定向。令点 u 经过定向后标号为 f_u，则需要求出所有 f_v>f_u 的 v 中 f_v 的最小值（定为 nxt_u），以及f_v<f_u 的 v 中 f_v 的最大值（定为 pre_u），通过 nxt 一条龙从 s 找到 t，再找到编号最大的未选中的点，通过 pre 一条龙找到 s。这一系列下来恰好可以找到一个完整的环。

因此套用上文的内容可以通过本题。时间复杂度 O(n \log n)，瓶颈在于排序。

代码如下：

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,c,M;
const int N_=1000050;
vector<int>rt,g[N_],ans[N_],Ans;
int vis[N_],f[N_],pos;
int dfn[N_],low[N_],stk[N_],cnt,tp,N,q;
vector<int>t[N_],U[N_],V[N_];
bool cmp(int,int);
void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    stk[++tp]=x;
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
            if(low[v]==dfn[x]){
                ++N;
                int u=0;
                while(u!=v){
                    u=stk[tp--];
                    t[u].push_back(N);
                    t[N].push_back(u);
                    M++;
                }
                t[x].push_back(N);
                t[N].push_back(x);
                M++;
            }
        }else low[x]=min(low[x],dfn[v]);
    }
}
int B[N_];
namespace BP{
    int dfn[N_],low[N_],cnt,fa[N_],rdf[N_],on[N_],vis[N_];
    void tar(int x,int pa){
        dfn[x]=low[x]=++cnt;fa[x]=pa,rdf[cnt]=x;
        for(int i=0;i<U[x].size();i++){
            int v=U[x][i];if(v==pa)continue;
            if(!dfn[v])tar(v,x),low[x]=min(low[x],low[v]);
            else low[x]=min(low[x],dfn[v]);
        }
    }
    vector<int>ans,p[N_];
    int CNT;//调试用的变量。别管它。
    void dfs(int x){
        CNT++;
        vis[x]++,ans.push_back(x),B[x]=ans.size();
        for(int i=0;i<p[x].size();i++)if(!vis[p[x][i]])dfs(p[x][i]);
    }
    void bipolar(int s,int t,vector<int>&V){
        //清空
        for(int i=0;i<V.size();i++)
            on[V[i]]=0,p[V[i]].clear(),vis[V[i]]=0,dfn[V[i]]=0;
        cnt=0,ans.clear();
        CNT=0;
        //建树
        tar(s,0);
        //确定路
        vector<int>path;
        for(int now=t;now;now=fa[now])on[now]=1,path.push_back(now);
        //剥叶子
        for(int i=cnt;i>0;i--){
            int u=rdf[i];
            if(!on[u])
                p[fa[u]].push_back(u),p[rdf[low[u]]].push_back(u);
        }
        //计算答案 
        int s1=0,s2=0;
        int tmp=ans.size();
        for(int i=0;i<V.size();i++)
            s1+=vis[V[i]];
        for(int i=path.size()-1;i>=0;i--){
            dfs(path[i]);
        }
        //清空列表 
        for(int i=0;i<V.size();i++)
            s2+=vis[V[i]];
        for(int i=0;i<V.size();i++)on[V[i]]=0,p[V[i]].clear();cnt=0;

    }

}
int nxt[N_],pre[N_];
void dfs(int x,int fa){
    vis[x]=1;
    if(x<=n){//round 
        f[x]=x;
        //get f 
        for(int i=0;i<t[x].size();i++){
            int v=t[x][i];if(v!=fa)dfs(v,x),f[x]=min(f[x],f[v]);
        }
        //sort
        sort(t[x].begin(),t[x].end(),cmp);
    }else{//square 
        f[x]=n+1;
        //sort 

        vector<int>&R=t[x];
        int Q=R.size();
        //建图 
        for(int i=0;i<R.size();i++)
            B[R[i]]=1,nxt[R[i]]=0x3f3f3f3f,pre[R[i]]=0;
        for(int i=1;i<R.size();i++){if(R[i]==fa)swap(R[0],R[i]);} 
        for(int i=0;i<R.size();i++){
            int v=R[i];
            if(v!=fa){
                for(int i=0;i<g[v].size();i++){
                    int vv=g[v][i];
                    if(B[vv])U[v].push_back(vv);
                    if(vv==fa)U[fa].push_back(v);
                } 
            }
        }
        //选一条边
        int S=fa,T=U[fa][0];
        //双极定向
        BP::bipolar(S,T,R);

        for(int i=0;i<BP::ans.size();i++){
            int u=BP::ans[i];
            for(int j=0;j<U[u].size();j++){
                int v=U[u][j];
                if(B[v]>B[u])nxt[u]=min(nxt[u],B[v]);
                else pre[u]=max(pre[u],B[v]);
            }
        }
        R.clear();
        for(int now=S;now!=T;now=BP::ans[nxt[now]-1])
            R.push_back(now),B[now]=0;
        R.push_back(T),B[T]=0;
        for(int i=BP::ans.size()-1;i>=0;i--){
            int u=BP::ans[i];
            if(B[u]){
                for(int now=u;now!=S;now=BP::ans[pre[now]-1])
                    R.push_back(now);
                break;
            }
        } 
        //get f
        for(int i=0;i<R.size();i++){
            int v=R[i];
            U[v].clear(),B[v]=0,nxt[v]=0,pre[v]=0;
        }
        for(int i=0;i<t[x].size();i++){
            int v=t[x][i];if(v!=fa)dfs(v,x);
        }
        if(f[t[x][1]]>f[t[x][t[x].size()-1]]){
            reverse(t[x].begin()+1,t[x].end());
        }
        f[x]=f[t[x][1]];

    }
}
void dfs2(int x,int q,int fa){
    vis[x]=1;
    if(x<=n){//round    
        int flag=0;
        for(int i=0;i<t[x].size();i++){
            int v=t[x][i];
            if(v==fa)continue;
            if(f[v]>x){
                if(flag==0){flag=1;ans[q].push_back(x);}
            }
            dfs2(v,q,x);
        }
        if(flag==0){
            flag=1;
            ans[q].push_back(x);
        }
    }else{//square
        for(int i=1;i<t[x].size();i++){
            dfs2(t[x][i],q,x);
        } 
    }
}
void purslane(int x){
    for(int i=0;i<ans[x].size();i++){
        while(pos!=rt.size()&&ans[x][i]>rt[pos]){
            pos++;
            purslane(pos-1);
        }
        Ans.push_back(ans[x][i]);
    }
}
bool cmp(int a,int b){
    return f[a]<f[b];
}
void solve(){
    scanf("%d%d",&n,&m);
    rt.clear();pos=0;
    N=n,M=m;
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            rt.push_back(i);
            tarjan(i),dfs(i,0);
        }
    }
    for(int i=1;i<=N;i++){
        vis[i]=0;
    for(int i=0;i<rt.size();i++){
        dfs2(rt[i],i,0);
    }
    while(pos<rt.size())pos++,purslane(pos-1);
    for(int i=0;i<Ans.size();i++){
        printf("%d ",Ans[i]);
    }
    printf("\n");
    for(int i=1;i<=N;i++)g[i].clear(),t[i].clear();
    for(int i=0;i<rt.size();i++)ans[i].clear();
    Ans.clear();
    for(int i=1;i<=N;i++){
        vis[i]=0,dfn[i]=0;
    }
}
int main(){
    freopen("graperm4.in","r",stdin);
    freopen("graperm4.out","w",stdout);
    int T; 
    scanf("%d%d",&c,&T);
    while(T--){
        solve();
    }
    return 0;
}