题解：P11726 [JOIG 2025] 最悪の記者 5 / Worst Reporter 5

· · 题解

这篇题解可能会比较详细，思维会比较连贯，由浅入深。

做法

考虑如果没有任何限制，那最终答案的排列 p 为 \{1,2,...,n\}。

接下来我们考虑这些限制的本质就是要求每次“交换”前 a_i,b_i 是相邻的。

我们先来看最无脑的限制：a_n,b_n。

我们发现在最终答案中，a_n 和 b_n 必须是相邻的，虽然很废话，但也是具有启发性的。

再往前想一步，我们把 a_n,b_n 在答案序列里交换回去，发现 a_{n-1},b_{n-1} 在交换后的序列里也必须是相邻的。

接着交换 a_{n-1},b_{n-1} 后，对于 a_{n-2},b_{n-2} 的要求也是一样的。

这启发我们可以倒着做，因为虽然我们不知道在这么多限制下最终的序列是什么样的，但我们知道理想中的（字典序最小的）序列是什么样的。而对于初始序列，我们可以得到的信息更加有限，况且我们无法知道什么样的初始序列会在一系列操作后得到字典序较小的最终序列。

其实看到“二元关系”就会比较自然的想到图论建模，这还是比较套路的。

于是我们尝试对 a_i,b_i 连边，发现卡住了。

思考对 a_i,b_i 连边做不下去的原因：每次操作后对后面的局面是有影响的，所以无法在同一张图上，体现不同“时间”下的相邻关系。

那么我们尝试把“时间”统一化，统一成最后时刻的关系。

设 f_i 表示现在 i 所处的位置是哪个元素的最终位置，初始时 f_i 为理想答案下的状态，即 f_i=i。

听上去有点绕，我们举个例子（阅读理解能力较强的读者可跳过）：若 f=\{3,1,2,5,4\},ans=\{2,1,3,4,5\}，则现在的局面是 p=\{3,2,1,5,4\}。

那么我们每次对 f_{a_i},f_{b_i} 连边，然后交换 f_{a_i},f_{b_i}，因为交换 a_i,b_i 就是在交换最终局面中对应位置元素的位置。

现在考虑该如何判定无解。我们都知道一个元素的相邻元素最多只有 2 个，且不可能每个元素都有 2 个相邻的元素，首尾两个元素是只有 1 个相邻元素的。这个约束在图上的体现就是：每个连通块都必须是一条链（允许重边）。

所以每次我们只需判一下是否有环、是否有分叉（点的度数 \ge 3）即可。

有解情况的方案是比较简单的，我们定义“链头”为链两端中较小的一端，每次取“链头”较小的一条链，按照顺序排列即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
bool vis[N];
int n,m,a[N],b[N],deg[N],f[N],tp[N],tot=0;
vector<int> lnk[N],G[N],now,p;
unordered_map<int,bool> e[N];
void dfs(int u,int fu) {
    if (vis[u]) {cout<<"No\n"; exit(0);}
    vis[u]=1,now.push_back(u);
    for (int v:G[u])
        if (v!=fu) dfs(v,u);
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=m;i++) cin>>a[i]>>b[i];
    for (int i=m;i>=1;i--) {
        int u=f[a[i]],v=f[b[i]];
        swap(f[a[i]],f[b[i]]);
        if (e[u][v]) continue;
        G[u].push_back(v),G[v].push_back(u),deg[u]++,deg[v]++,e[u][v]=e[v][u]=1;
    }
    for (int i=1;i<=n;i++)
        if (deg[i]>2) {cout<<"No\n"; exit(0);}
    int siz;
    for (int i=1;i<=n;i++) {
        if (!deg[i]) lnk[++tot].push_back(i),tp[i]=tot,vis[i]=1;
        else if (deg[i]==1&&!vis[i]) {
            now.clear(),dfs(i,0);
            siz=now.size(),tot++;
            if (now[siz-1]<i) {
                for (int j=siz-1;j>=0;j--) lnk[tot].push_back(now[j]);
                tp[now[siz-1]]=tot;
            }
            else {
                for (int j=0;j<siz;j++) lnk[tot].push_back(now[j]);
                tp[now[0]]=tot;
            }
        }
    }
    for (int i=1;i<=n;i++)
        if (!vis[i]) {cout<<"No\n"; exit(0);}
    for (int i=1;i<=n;i++)
        if (tp[i]) {for (int x:lnk[tp[i]]) p.push_back(x);}
    cout<<"Yes\n";
    for (int x:p) cout<<x<<"\n";
    return 0;
}