正经题解｜序列X

题目大意

有一个长度为 $n$ 序列 $x$，$x$ 是个排列。你可以通过一次变换操作，得到一个新的序列，将序列中任意一个数，移动到 $x$ 的头部。

题意分析

给你 $k$ 个序列，是否能找到 $x$ 序列，使得这 $k$ 个序列由 $x$ 得到。

解题思路

假设现在有个序列为 $2,3,4,1,5$。
我变换两个序列出来 $3,2,4,1,5$，$4,2,3,1,5$。
我们可以发现虽然变化后，除去头部，$3$ 的位置一定在 $4,1,5$ 的前面，$4$ 的位置一定在 $1,5$ 的前面，$1$ 的位置一定在 $5$ 的前面。也就是说去除头部后，后面元素的相对位置是不变的。

对于顺序关系，我们很容易想到拓扑排序，我们去除序列的头部，依次建边，如果存在有向无环图则说明后面部分的相对顺序全部正确，反之错误。

时间复杂度分析

拓扑排序的复杂度为：$O(V + E)$，其中 $V$ 表示图中顶点的个数，$E$ 表示图中边的数量。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> v[N];
int a[N];
int in[N];
int t,n,k,x;
void solve() {
    queue<int> q;
    for(int i=1;i<=n;i++)if (!in[i])q.push(i);
    int cnt = 0;
    while(!q.empty()) {
        cnt++;
        int cur = q.front();
        q.pop();
        for(int i:v[cur]) {
            if (!(--in[i]))q.push(i);
        }
    }
    if (cnt == n) {
        cout << "YES" << endl;
    }else {
        cout << "NO" << endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while(t--) {
        cin >> n >> k;
        for(int i=1;i<=n;i++){
            in[i] = 0;
            v[i].clear();
        }
        for(int i=0;i<k;i++) {
            for(int j=0;j<n;j++) cin >> a[j];
            for(int j=1;j+1<n;j++) {
                v[a[j]].push_back(a[j+1]);
                in[a[j+1]]++;
            }
        }
        solve();
    }
    return 0;
}