CF915D Almost Acyclic Graph
题目描述
给定一个包含 $n$ 个顶点和 $m$ 条边的有向图（每条边都是有方向的，只能沿着其方向遍历），你最多可以删除一条边。
你能否通过删除至多一条边，使得这个有向图变成无环图？一个有向图被称为无环图，当且仅当它不包含任何环（即不存在非空路径起点和终点为同一个顶点）。
输入格式
第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 500$，$1 \leq m \leq \min(n(n-1), 100000)$），表示顶点数和边数。
接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示一条从顶点 $u$ 指向顶点 $v$ 的有向边（$1 \leq u,v \leq n$，$u \ne v$）。每对有序对 $(u,v)$ 最多出现一次（即从 $u$ 到 $v$ 的有向边最多只有一条）。
输出格式
如果可以通过删除至多一条边使得图变为无环图，输出 YES。否则，输出 NO。
说明/提示
在第一个样例中，你可以删除边 ，使图变为无环图。
在第二个样例中，至少需要删除两条边（例如  和 ），才能使图无环。
由 ChatGPT 5 翻译