原题链接

题解

每张截图除了第一个人，其余人均按相对位置排序
这道题就变成了给定若干个相对位置，求是否存在可能的绝对位置
我们可以建图，作拓扑排序，一个节点能被遍历到当且仅当其所有的父节点都被遍历到
当且仅当出现环时，答案为NO

code

#include<bits/stdc++.h>
using namespace std;
vector<int> G[200005];
int in[200005]={0};
int a[200005]={0};
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;

        for(int i=1;i<=n;i++)
        {
            G[i].clear();
            in[i]=0;
        }

        while(m--)
        {
            for(int i=1;i<=n;i++)
            {
                cin>>a[i];
                if(i>=3)
                {
                    G[a[i-1]].push_back(a[i]);
                    in[a[i]]++;
                }
            }
        }

        queue<int> q;
        for(int i=1;i<=n;i++)  if(!in[i]) q.push(i);

        int cnt=0;
        while(q.size())
        {
            int now=q.front();
            cnt++;
            q.pop();

            for(auto next:G[now])
                if(--in[next]==0)  q.push(next);
        }
        puts((cnt==n)?"YES":"NO");
    }
    return 0;
}