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

· · 题解

\color{blue}{\texttt{[Analysis]}}

思路参考了官方题解。

赋值操作的特点是最终的结果只和最后一次赋值操作有关。

构造这么一张有向图 G：边 i \to j 存在当且仅当 i<j，且操作 p_{i} 和 p_{j} 同时对某个位置 t 进行了重赋值，且 j 是最后一次对 t 进行了赋值的操作。

满足了这三个条件，则在原来的操作顺序下，t 位置最终一定是 j 而不是 i。因此在合法的答案中，j 也必须在 i 的后面，不然 t 位置的值就改变了。

当然我们不能显式的把图 $G$ 建立，因为那样图可能很大，且不方便寻找满足条件的拓扑序。 因为只要输出一个合法方案就行，我们考虑限制一下我们的操作。不妨考虑只能交换相邻的两个操作。 > 定理：如果存在合法的方案，则一定存在一种方案，它只交换了相邻的两个操作。 > > - 证明： > - 如果不存在这样的方案，则代表原图存在所有的 $(i-1) \to i$ 的边（$2 \leq i \leq n,i \in \mathbb{N}$）。 > - 那么原图的拓扑序就只有 $1 \to 2\to 3 \to 4 \to \dots \to n$ 这一种，不存在其它的合法方案。 > - 因此，如果存在合法方案，一定存在一种方案，只交换了相邻的两个操作。 因此只需要对相邻的两个操作进行判断即可。 $\color{blue}{\text{Code}} 
const int N=1e5+100;

int p[N],n,m,ans[N],lst[N];
vector<int> pos[N];

void init(int n,int m){
    for(int i=1;i<=n;i++) ans[i]=i;
    for(int i=1;i<=n;i++) pos[i].clear();
    for(int i=1;i<=m;i++) lst[i]=0;
}

int OZDY(){
    n=read();m=read();

    init(n,m);

    for(int i=1;i<=n;i++){
        p[i]=read();
        for(int j=1;j<=p[i];j++){
            int u=read();
            pos[i].push_back(u);
            lst[u]=i;
        }

        sort(pos[i].begin(),pos[i].end());
    }

    bool Flag=false;

    for(int i=2;i<=n;i++){
        bool flag=true;

        for(int u:pos[i]){
            auto tmp=lower_bound(pos[i-1].begin(),pos[i-1].end(),u);
            if (tmp!=pos[i-1].end()&&(*tmp==u)&&i==lst[u]){
                flag=false;break;
            }
        }

        if (flag){
            Flag=true;
            swap(ans[i],ans[i-1]);
            break;
        }
    }

    if (Flag){
        printf("Yes\n");
        for(int i=1;i<=n;i++)
            printf("%d%c",ans[i],(i==n?'\n':' '));
    }
    else printf("No\n");

    return Flag;
}

int main(){
    int T=read();
    while (T--) OZDY();

    return 0;
}