题解归档 - cf2237E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2237E
• 本地来源：problems/cf2237E/idea.md
• 题目链接：https://codeforces.com/contest/2237/problem/E
• 原始标题：Codeforces 2237E - Permutation Commutation 详细题解

思路

Codeforces 2237E - Permutation Commutation 详细题解

1. 核心数学本质：等式到底在说什么？

题目要求构造一个字典序最小的排列 $b$（代码中的 p），使得对于所有的 $i$，都有 $a_{b_i} = b_{a_i}$（代码中 $a$ 数组是 s）。

这个等式其实是函数复合的交换律：$a(b(i)) = b(a(i))$。

把它放到“图论”或者“排列”的视角里，排列 $a$ 可以被拆解成若干个互不相交的环（Cycles）。
假设 $a$ 中有一个环：$1 \xrightarrow{a} 2 \xrightarrow{a} 3 \xrightarrow{a} 1$。
如果我们对这个环上的元素套用 $b$ 的映射，会发生什么？

• $b_2 = b_{a_1} = a_{b_1}$
• $b_3 = b_{a_2} = a_{b_2} = a_{a_{b_1}}$

核心结论：

1. 牵一发而动全身：在 $a$ 的同一个环里，只要你确定了其中任意一个元素的 $b$ 值，这个环上所有其他元素的 $b$ 值就顺藤摸瓜全部唯一确定了！
2. 环映射到环：$b$ 的作用，本质上是把 $a$ 中的一个环，整体映射到了 $a$ 中的另一个环上。而且，这两个环的长度必须完全相等。

2. 代码的详细实现步骤

基于上面的结论，我们的代码分为了四个明确的步骤：

第一步：找环并计算环的大小 (并查集 DSU)

for(i=1;i<=n;i++) f[find(i)]=find(s[i]); // 并查集连边，把同一个环的元素合并
for(i=1;i<=n;i++) fs[find(i)]++;         // 统计每个环的长度 (fs 数组)

这里用并查集把 $a$ 数组（代码里的 s）中的环找出来。find(i) 代表 $i$ 所在环的代表元素，fs[find(i)] 就是这个环的长度。

第二步：顺藤摸瓜，补全已知的映射 (Propagate)

题目已经给出了一部分 $b_i$（代码里的 p 数组，未知的是 -1）。我们要把这些已知信息扩散到整个环。

for(i=1;i<=n;i++){
    if(p[i]!=-1 && !vis_cycle[find(i)]){ // 如果这个位置已知，且它所在的环还没被推导过
        vis_cycle[find(i)]=1;            // 标记这个环已处理，防止 TLE
        if(fs[find(i)]!=fs[find(p[i])]){ // 冲突1：如果映射的两个环长度不一样，绝对无解
            pd=0; break;
        }
        a=i, b=p[i];
        zc=fs[find(i)];
        for(j=1;j<=zc;j++){              // 沿着环转一圈，把整个环的 p 值都填上
            if(p[a]!=-1 and p[a]!=b){    // 冲突2：推导出的值和题目原本给的值不一样，矛盾！
                pd=0; break;
            }
            p[a]=b;                      // 填入推导出的值
            a=s[a], b=s[b];              // 两个环同步往后走一步：a = s[a], b = s[b]
        }
    }
}

注意这里的一个神级优化：vis_cycle。如果一个环里有多个元素已知，我们只需要推导一次就够了。如果不加这个标记，极端情况下（比如一个长度为 $N$ 的大环，所有元素都已知）会退化成 $O(N^2)$ 导致 TLE。

第三步：检查目标是否被重复占用 (Permutation 属性)

for(i=1;i<=n;i++){
    if(p[i]!=-1){
        if(pdpd[p[i]]==1){ pd=0; break; } // 冲突3：多个不同的环映射到了同一个目标，导致数字重复！
        pdpd[p[i]]=1;                     // 标记该数字已被作为目标使用
    }
}

因为 $b$ 必须是一个排列，每个数字只能出现一次。如果推导完发现两个不同的元素指向了同一个数字，说明无解。

第四步：贪心填补未知，要求字典序最小 (Greedy Assignment)

现在剩下的就是那些完全没有被分配的环了。我们要给它们分配目标环。
为了让字典序最小，我们从前到后遍历 $i$，如果 $p_i = -1$，我们就希望给它分配一个尽可能小的合法值。

// 1. 把所有还没被当成目标的元素，按它们所在环的长度分类，存入 set 中
for(i=1;i<=n;i++){ 
    if(pdpd[i]==0){ 
        cccc[fs[find(i)]].insert(i);
    }
}

// 2. 贪心分配
for(i=1;i<=n;i++){ 
    if(p[i]==-1){
        ll len=fs[find(i)];
        if(cccc[len].empty()){ pd=0; break; } // 冲突4：找不到长度相等的空闲环了，无解
        
        b=*cccc[len].begin(); // 贪心：从 set 中取出长度匹配且【最小】的可用元素
        a=i;
        for(j=1;j<=len;j++){  // 同样顺藤摸瓜，把这两个环绑定
            p[a]=b;
            cccc[len].erase(b); // 用过了就从 set 里删掉
            a=s[a];
            b=s[b];
        }
    }
}

这里用 set<ll> cccc[len] 是非常巧妙的。它把所有“闲置”的元素按所在环的长度 len 进行了分组。因为 set 内部是有序的，所以每次调用 *cccc[len].begin() 拿到的绝对是当前长度下最小的那个元素，完美契合了题目“字典序最小”的要求。

总结

1. 找环：把 $a$ 拆成一个个环。
2. 推导：利用已知条件，把能确定的环全部确定下来，顺便检查长度是否匹配、内部是否矛盾。
3. 查重：检查有没有两个环撞车映射到了同一个地方。
4. 贪心：把剩下的空环，按长度匹配，每次挑最小的闲置元素接上去。

整个算法的时间复杂度是 $O(N \log N)$（主要来自于 set 的插入和删除），逻辑非常严密。

代码

来源：problems/cf2237E/solution.cpp

/* Author: likely
 * Time: 2026-06-18 23:29:14
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5;
ll s[maxn+5],p[maxn+5],f[maxn+5],fs[maxn+5];
bool pdpd[maxn+5],pdpd2[maxn+5];
set<ll>cccc[maxn+5];
ll find(ll x){
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
int main(){
    ll t,n,i,j,k,pd,a,b,zc;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n),pd=1;
        for(i=1;i<=n;i++) scanf("%lld",&s[i]);
        for(i=1;i<=n;i++) scanf("%lld",&p[i]);
        for(i=1;i<=n;i++) f[i]=i,fs[i]=0,pdpd[i]=0,cccc[i].clear(),pdpd2[i]=0;
        for(i=1;i<=n;i++) f[find(i)]=find(s[i]);
        for(i=1;i<=n;i++) fs[find(i)]++;
        for(i=1;i<=n;i++){
            if(p[i]!=-1 and pdpd2[find(i)]==0){
                pdpd2[find(i)]=1;
                if(fs[find(i)]!=fs[find(p[i])]){
                    pd=0;
                    break;
                }
                a=i,b=p[i];
                zc=fs[find(i)];
                for(j=1;j<=zc;j++){
                    if(p[a]!=-1 and p[a]!=b){
                        pd=0;
                        break;
                    }
                    p[a]=b;
                    a=s[a],b=s[b];
                }
                if(pd==0) break;
            }
        }
        if(pd==0){
            printf("NO\n");
            continue;
        }
        for(i=1;i<=n;i++){
            if(p[i]!=-1){
                if(pdpd[p[i]]==1){
                    pd=0;
                    break;
                }
                pdpd[p[i]]=1;
            }
        }
        if(pd==0){
            printf("NO\n");
            continue;
        }
        for(i=1;i<=n;i++){
            if(pdpd[i]==0){
                cccc[fs[find(i)]].insert(i);
            }
        }
        for(i=1;i<=n;i++){
            if(p[i]==-1){
                zc=fs[find(i)];
                if(cccc[zc].empty()){
                    pd=0;
                    break;
                }
                a=i,b=*cccc[zc].begin();
                for(j=1;j<=zc;j++){
                    p[a]=b;
                    cccc[zc].erase(b);
                    a=s[a],b=s[b];
                }
            }
        }
        if(pd==0) printf("NO\n");
        else{
            printf("YES\n");
            for(i=1;i<=n;i++) printf("%lld%c",p[i],i==n?'\n':' ');
        }
        for(i=1;i<=n;i++) cccc[i].clear();
    }
    return 0;
}