题解：P13956 [ICPC 2023 Nanjing R] 等价重写

· · 题解

我是奶龙，此言不假。

先求出来每一个位置最后是哪个操作染的色。

然后倒序考虑，容易发现每一个操作其拥有的颜色的最终操作必然得在当前操作之后。

考虑从最终操作这个位置向当前操作建边，然后容易想到跑一个拓扑，只要队列里同时有两个数，那么显然可以交换。

于是做完了。

#include<bits/stdc++.h>
using namespace std;
int f[100005];
vector<int>ve[100005];
vector<int>sum[100005];
vector<vector<int>>a;
void solve(){
    vector<int>ans;
    a.clear();
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    sum[i].clear();
    ve[n+1].clear();
    for(int i=1;i<=n;i++)
    f[i]=1,ve[i].clear(),
    ve[n+1].push_back(i);
    a.push_back({});
    for(int i=1;i<=n;i++){
        vector<int>flc;
        int p;
        cin>>p;
        while(p--){
            int x;
            cin>>x;
            flc.push_back(x);
        }
        a.push_back(flc);
    }
    for(int i=n;i;i--){
        for(int j=0;j<a[i].size();j++){
            for(int k=0;k<sum[a[i][j]].size();k++){
                ve[sum[a[i][j]][k]].push_back(i);
                f[i]++;
            }
            if(sum[a[i][j]].size())continue;
            sum[a[i][j]].push_back(i);
        }
    }
    queue<int>q;
    q.push(n+1);
    map<int,bool>mp;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(x!=n+1)ans.push_back(x);
        if(q.size()&&mp.empty()){
            mp[x]=mp[q.front()]=(q.front()<x);
        }
        for(int i=0;i<ve[x].size();i++){
            f[ve[x][i]]--;
            if(f[ve[x][i]])continue;
            q.push(ve[x][i]);
        }
    }
    if(mp.empty()||ans.size()!=n){
        puts("No");
        return;
    }
    reverse(ans.begin(),ans.end());
    for(int i=1;i<ans.size();i++)
    if(mp[ans[i]]&&mp[ans[i-1]])
    swap(ans[i],ans[i-1]);
    puts("Yes");
    for(int i=0;i<ans.size();i++)
    cout<<ans[i]<<' ';cout<<'\n';
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

说好相临难度不改来着，怎么就绿降黄了……？