P5470. 推理模型分批约束

场次：2026年9月18日-非AI方向 · 来源：CodeFun2000 P5470

题目描述

一次偏复杂的推理会拉起若干模型，每一份都对应一个整型编号（若份数是 $6$ ，编号便是 $1,2,3,4,5,6$ ）。各模型可能有先后约束：前一份产出会作为后一份的入口，这些约束登记在表 $rel$ 中。

已知模型份数 $p$ 以及约束表 $rel$ 。第 $k$ 条若写作 $rel[k]=[u,v]$ ，意思是编号 $v$ 必须等编号 $u$ 先结束，也就是 $u$ 要排到 $v$ 前面。

请把这次推理里的模型切成若干波次来跑；同一波次内彼此没有先后约束，因此允许同时开工。请给出最少要切几波，才能让全部模型都跑完。

下面这 $5$ 份模型的先后约束可以当作例子：

编号 $1$ 与 $5$ 都要等 $4$ 结束，编号 $2$ 与 $3$ 都要等 $5$ 结束。于是先跑 $4$ ，再让 $1$ 、 $5$ 同时跑，最后让 $2$ 、 $3$ 同时跑，合计 $3$ 波。

注意：

1、各模型保证不会形成环形等待。

限制范围：

$1\le p\le 10^{5}$

$0\le e\le\min(p\times(p-1),1.5\times 10^{6})$

$p$ ：整数，模型份数。

$e$ ：整数，先后约束一共有几条。

随后给出 $e$ 行，每一行两个模型编号，用来标明这一对谁先谁后。

一个整数，即最少要安排的波次数。

输入：

输出：

说明：

一共 $6$ 份模型。先后约束是： $1$ 等 $2$ ， $5$ 等 $2$ ， $4$ 等 $1$ 也等 $5$ ， $6$ 等 $3$ 。

可按 $(2,3)\to(1,5,6)\to(4)$ 安排：第一波同时跑 $2$ 与 $3$ ，第二波同时跑 $1$ 、 $5$ 、 $6$ ，第三波跑 $4$ 。最少 $3$ 波。

输入：

输出：

说明：

一共 $5$ 份模型。先后约束是： $3$ 等 $5$ ， $2$ 等 $3$ ， $1$ 等 $2$ ， $4$ 等 $1$ 。只能沿 $5\to 3\to 2\to 1\to 4$ 依次开跑，需要 $5$ 波。