题解 | 2023 年牛客多校第三场 J 题 Fine Logic

题意：给定 $nn$ 个点和 $mm$ 对偏序关系 $⟨u,v⟩\backslash langle\; u,v\backslash rangle$，构造最少的排列数目 $kk$，使得在这 $kk$ 个排列中至少有一个排列满足 。$1\le n,m\le 10^{6}1\backslash le\; n,m\; \backslash le\; 10^6$。

解法：数据范围过于庞大意味着 $kk$ 必然不大。其实很容易发现一种任意情况下都成立的方案：$k=2k=2$，一个排列是 $\{1,2,3,\cdots ,n\}\backslash \{1,2,3,\backslash cdots,n\backslash \}$，另一个排列是 $\{n,n-1,n-2,\cdots ,1\}\backslash \{n,n-1,n-2,\backslash cdots,1\backslash \}$。因为 的情况在第一个排列中，$u>vu>v$ 在第二个排列中。

考虑什么时候满足 $k=1k=1$。如果 $k=1k=1$，则必然存在一个拓扑序列。考虑依照 $u\to vu\; \backslash rightarrow\; v$ 建图，即必须访问完 $uu$ 才能访问 $vv$。如果该 DAG 有拓扑序，那么这个排列就是合法的。否则则按 $k=2k=2$ 的方案构造。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
int in[N + 5];
vector<int> G[N + 5];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        in[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i])
            q.push(i);
    vector<int> ans;
    while (!q.empty())
    {
        int tp = q.front();
        q.pop();
        ans.push_back(tp);
        for (auto x : G[tp])
        {
            in[x]--;
            if (!in[x])
                q.push(x);
        }
    }
    if (ans.size() == n)
    {
        printf("1\n");
        for (auto x : ans)
            printf("%d ", x);
    }
    else
    {
        printf("2\n");
        for (int i = 1; i <= n; i++)
            printf("%d ", i);
        printf("\n");
        for (int i = n; i >= 1; i--)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}