← 返回题目列表

Codeforces · 1674/G

G. 删除定向边

中文机器翻译题面 查看原题

给定一个有向无环图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。顶点编号从 $$$1$$$ 到 $$$n$$$。不存在重边和自环。

令 $$$\mathit{in}_v$$$ 为传入边的数量(入度),$$$\mathit{out}_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$$$。

如果对于每对顶点 $$$v$$$ 和 $$$u$$$ ($$$v \neq u$$$) 使得 $$$v \in S$$$ 和 $$$u \in S$$$ 存在一条从 $$$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$$$) - 边的描述。

给定的边形成有效的有向无环图。不存在多重边。

输出

打印单个整数 - 从图中删除一些边并且所有顶点的入度和出度都减小或保持等于 $$$0$$$ 后可爱集合 $$$S$$$ 的最大可能大小。

示例

输入 #1

3 3
1 2
2 3
1 3

输出 #1

2

输入 #2

5 0

输出 #2

1

输入 #3

7 8
7 1
1 3
6 2
2 3
7 2
2 4
7 3
6 3

输出 #3

3

注意

在第一个示例中,您可以删除边 $$$(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)$$$,答案不会改变。

这是第三个示例中的图表图片: