CF1674G Remove Directed Edges

给定一个有 $n$ 个顶点和 $m$ 条边的有向无环图（DAG）。顶点编号为 $1$ 到 $n$。图中没有重边和自环。 令 $\mathit{in}_v$ 表示顶点 $v$ 的入度，$\mathit{out}_v$ 表示顶点 $v$ 的出度。 你可以从图中删除一些边。设新图中顶点 $v$ 的入度和出度分别为 $\mathit{in'}_v$ 和 $\mathit{out'}_v$。 你只能在满足以下条件的情况下删除边，对于每个顶点 $v$ 都要满足： - $\mathit{in'}_v < \mathit{in}_v$ 或 $\mathit{in'}_v = \mathit{in}_v = 0$； - $\mathit{out'}_v < \mathit{out}_v$ 或 $\mathit{out'}_v = \mathit{out}_v = 0$。 我们称一个顶点集合 $S$ 是“可爱”的，如果对于 $S$ 中任意两个不同的顶点 $v$ 和 $u$，在未被删除的边上，存在一条从 $v$ 到 $u$ 或从 $u$ 到 $v$ 的路径。 请问，在删除一些边并且所有顶点的入度和出度都减少或保持为 $0$ 后，“可爱”集合 $S$ 的最大可能大小是多少？

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 2 \cdot 10^5$），表示图的顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$，$v \neq u$），表示一条从 $v$ 到 $u$ 的有向边。 给定的边构成一个合法的有向无环图。不存在重边。

输出一个整数，表示在删除一些边并且所有顶点的入度和出度都减少或保持为 $0$ 后，“可爱”集合 $S$ 的最大可能大小。

在第一个样例中，你可以删除边 $(1, 2)$ 和 $(2, 3)$。$\mathit{in} = [0, 1, 2]$，$\mathit{out} = [2, 1, 0]$。$\mathit{in'} = [0, 0, 1]$，$\mathit{out'} = [1, 0, 0]$。可以看到所有 $v$ 都满足条件。最大“可爱”集合 $S$ 由顶点 $1$ 和 $3$ 组成，它们之间仍有一条直接的边，因此它们之间存在路径。 在第二个样例中，没有边。由于所有 $\mathit{in}_v$ 和 $\mathit{out}_v$ 都等于 $0$，所以保留一个没有边的图是允许的。共有 $5$ 个“可爱”集合，每个集合只包含一个顶点。因此最大大小为 $1$。 在第三个样例中，你可以删除边 $(7, 1)$、$(2, 4)$、$(1, 3)$ 和 $(6, 2)$。最大“可爱”集合为 $S = \{7, 3, 2\}$。你也可以删除边 $(7, 3)$，答案不会改变。 下图为第三个样例的图示：  由 ChatGPT 4.1 翻译