CF1682E 构造+拓扑排序

· · 题解

link

跟其他几篇题解不太一样。

思路

\text{Step 1}

对于一个排列 p，将 i 向 p_i 连边后可以得到一张由简单环和自环组成的有向图（以下提到的环都包括自环）（若此处连边反着连，后续讨论也要反过来）。

结论：假如图上共有 c 个环，那么将 p 还原的最小操作次数为 n-c。

为什么呢？

设图上环的数量为 \phi，初始时 \phi=c，目标状态是 \phi=n（\forall i,p_i=i，有 n 个自环）。

最优方案显然是一直让 \phi 增加 1，直到 \phi=n 结束。 也就是说，需要保证每一次交换都发生在同一个环内。

\text{Step 2}

考虑将这 m 次交换作为无向边加入到之前的有向图上，那么这些边初始时不可能跨环（两端点在不同环内），否则一定无解。

假设存在两条边 A,B，进行 A 的交换后会导致 B 跨环，考虑 A 和 B 的位置关系：

还剩下一种情况：A 和 B 共顶点。

读者可以自己手玩一下题目中的两个样例（其实是我太懒了不想画图），然后就会发现：对于这种情况，需要顺着环旋转的方向做交换，才能保证不跨环。

于是，再建一个以 m 条交换边作为顶点的新有向图记录这些"共顶点时顺着环旋转的方向做交换"的先后关系。最后拓扑排序一下，输出任意一个拓扑序即可。

复杂度 O(n\log n)，瓶颈在按旋转方向将边排序。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+7;
int to[N],rk[N],in[N],len[N],cir_cnt,deg[N],n,m,q[N];
vector<pii> G[N];//加入的无向交换边
vector<int> g[N];//新图
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,k,x,y;
    memset(rk,-1,sizeof rk); 
    cin>>n>>m;
    for(i=1;i<=n;++i) cin>>to[i];//to存储原有向图
    for(i=1;i<=m;++i) cin>>x>>y,G[x].emplace_back(y,i),G[y].emplace_back(x,i);
    //找环
    for(i=1;i<=n;++i)if(rk[i]==-1)
    {
        rk[i]=0,in[i]=++cir_cnt;//rk-环上的排名
        for(j=to[i],k=1;j!=i;j=to[j],++k) rk[j]=k,in[j]=cir_cnt;
        len[cir_cnt]=k;//环长
    }
    //排序 建新图
    for(i=1;i<=n;++i)
    {
        int L=len[in[i]],ri=rk[i];
        sort(G[i].begin(),G[i].end(),[&](pii x,pii y)
        {
            int rx=rk[x.first]<=ri?rk[x.first]+L:rk[x.first];
            int ry=rk[y.first]<=ri?rk[y.first]+L:rk[y.first];
            return rx<ry;
        });
        for(j=1;j<(int)G[i].size();++j)
            g[G[i][j-1].second].push_back(G[i][j].second),++deg[G[i][j].second];
    }
    //拓扑排序
    int hd=1,tl=0,u;
    for(i=1;i<=m;++i)if(deg[i]==0)q[++tl]=i;
    while(hd<=tl)
    {
        u=q[hd++],cout<<u<<' ';
        for(int v:g[u])if(!--deg[v])q[++tl]=v;
    }
    return 0;
}