CF1931F 题解

yyrwlj · 2024-02-14 13:35:01 · 题解

思路

每个人看到的顺序不能说明具体位置，但是给出了前后关系。对于第 i 个顺序，对于 j \in [2,n-1]，都能说明 a_{ij} 在 a_{ij+1} 前面。

所有前面的向后面的连边，最后拓扑排序看建出来的图是不是拓扑图。

拓扑排序判环：拓扑排序后有点没有入队过就代表有环。

每个 a_{ij} 只用向后面第一个连边，因为后面第一个会和后面第二个连边，一直到最后，它们肯定是联通的，判环不需要管中间有几条边，建出来这些边只会浪费时间和空间。

Code

#include <iostream>
using namespace std;
const int N = 200005;
struct Edge{
    int to, nxt;
}g[N];
int h[N], d[N], idx;
int a[N], q[N];
void add(int a,int b)
{
    g[++idx].to = b, g[idx].nxt = h[a], h[a] = idx;
    d[b] ++;
}
void work()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i=1;i<=n;i++)
        h[i] = d[i] = 0;
    idx = 0;
    for (int i=1;i<=k;i++)
    {
        for (int j=1;j<=n;j++)
            scanf("%d", &a[j]);
        for (int j=2;j<n;j++)
            add(a[j], a[j + 1]);
    }
    int hh = 0, tt = -1;
    for (int i=1;i<=n;i++)
        if (d[i] == 0)
            q[++tt] = i;
    while (hh <= tt)
    {
        int t = q[hh ++];
        for (int i = h[t]; i; i = g[i].nxt)
        {
            int j = g[i].to;
            if (--d[j] == 0)
                q[++tt] = j;
        }
    }
    for (int i=1;i<=n;i++)
        if (d[i] > 0)
        {
            puts("NO");
            return;
        }
    puts("YES");
}