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

· · 题解

思路

昨天写了一下，为了准备区域赛，其实整套题做的很烂，写一下题解复盘。

这道题其实就是基本的拓扑排序，不难发现一个点如果被几个数字先后染色，只要保证最后一个染色数字不变就行，因此就说明最后的这个数字是前面数字的上级。同理，这样对每个位置都找到一个这样的顺序，就可以构成一个类似食物链的结构，就是拓扑图。因此只要拓扑排序一下，就可以找到解。但是要和原来的不同，因此就要用优先队列，第一关键字的等级，第二关键字的编号。编号我们逆序即可，最后判断一下是不是原有的顺序就行。

代码

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;
const int N = 100005;
typedef pair<int, int>PII;
vector<int>paint[N];
vector<int>to[N];
vector<int>ans;
int cnt[N] = {}, f[N] = {};

int main(void) {
    int t;
    cin >> t;
    while (t--) {
        ans.clear();
        memset(cnt, 0, sizeof(cnt));

        priority_queue<PII, vector<PII>, greater<PII>>Q;
        int n, m, sum = 0;
        cin >> n >> m;

        for (int i = 1; i <= n; i++) {
            int num;
            cin >> num;

            for (int j = 1; j <= num; j++) {
                int k;
                cin >> k;

                paint[k].push_back(i);
                f[k] = i;
            }
        }

        for (int i = 1; i <= m; i++) {

            for (int j = 0; j < int(paint[i].size()) - 1; j++) {
                int u = paint[i][j];

                to[u].push_back(f[i]);
                cnt[f[i]]++;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!cnt[i])Q.push(make_pair(0, -i));
        }

        while (!Q.empty()) {
            int dp = Q.top().first, u = Q.top().second * (-1);
            Q.pop();
            ans.push_back(u);

            for (int i = 0; i < to[u].size(); i++) {
                int k = to[u][i];
                cnt[k]--;

                if (!cnt[k])Q.push(make_pair(dp + 1, k * (-1)));
            }
        }
        bool ok = false;

        for (int i = 0; i < ans.size(); i++) {
            if (ans[i] != i + 1) {
                ok = true;
                break;
            }
        }

        if (ok) {
            cout << "Yes" << endl;
            for (int i = 0; i < n; i++) cout << ans[i] << ' ';

            cout << endl;
        }
        else {
            cout << "No" << endl;
        }

        for (int i = 1; i <= m; i++) paint[i].clear();
        for (int i = 1; i <= n; i++)to[i].clear();
    }
    return 0;
}