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

· · 题解

图论建模。

令 id_i 表示 i 号运动员在最后一轮的 id_i 号运动员的位置。

倒着建边，初始 id_i=i。

每次对于 id_{x_i} 和 id_{y_i} 建边，表示 id_{x_i} 和 id_{y_i} 运动员在最后一轮相邻。

所以建边之后的 x 连接 y 表示 x 与 y 在最后一轮相邻。

然后若有度数大于二的，直接无解。

如果有环，直接无解。

其他情况，找到每个联通块度为一的最小点。

然后直接一一遍历即可。

#include<bits/stdc++.h>
using namespace std;
struct FSI{
    template<typename T>
    FSI& operator >> (T &res){
        res=0;T f=1;char ch=getchar();
        while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
        while (isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
        res*=f;
        return *this;
    }
}scan;
const int N=6e5+10,M=1e6+10;
int n,m,i,x[M],y[M]; 
int last[N],c;
int id[N];
int ans[N],k,d[N];
bool vis[N],v[M];
struct Node{
    int to,next;
}a[M<<1];
struct node{
    int u,v;
}e[M];
void add(int u,int v)
{
    a[++c]={v,last[u]};
    last[u]=c;
}
void dfs(int x)
{
    int i,to;
    vis[x]=true;
    ans[++k]=x;
    for (i=last[x];i;i=a[i].next)
    {
        to=a[i].to;
        if (!vis[to]) dfs(to);
    }
}
bool cmp(node x,node y){return x.u<y.u||(x.u==y.u&&x.v<y.v);}
int main()
{
    scan>>n>>m;
    for (i=1;i<=m;i++) scan>>x[i]>>y[i];
    for (i=1;i<=n;i++) id[i]=i;
    for (i=m;i>=1;i--)
    {
        e[i]={id[x[i]],id[y[i]]};
        if (id[x[i]]>id[y[i]]) swap(e[i].u,e[i].v);
        swap(id[x[i]],id[y[i]]);
    }
    sort(e+1,e+m+1,cmp);
    for (i=1;i<=m;i++)
    {
        if (e[i].u==e[i-1].u&&e[i].v==e[i-1].v) v[i]=true;
    }
    for (i=1;i<=m;i++)
    {
        if (!v[i])
        {
            add(e[i].u,e[i].v);
            add(e[i].v,e[i].u);
            d[e[i].u]++;
            d[e[i].v]++;
        }
    }
    for (i=1;i<=n;i++) if (d[i]>2){puts("No");return 0;}
    for (i=1;i<=n;i++)
    {
        if (!vis[i])
        {
            if (!d[i]) ans[++k]=i,vis[i]=true;
            else if (d[i]==1) dfs(i);
        }
    }
    if (k!=n){puts("No");return 0;}
    puts("Yes");
    for (i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}