AT_abc292_e [ABC292E] Transitivity

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的简单有向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边是从顶点 $u_i$ 指向顶点 $v_i$ 的有向边。

你可以进行如下操作，操作次数不限（可以为 $0$ 次）：

• 选择两个不同的顶点 $x, y$，且当前不存在从 $x$ 到 $y$ 的有向边，然后添加一条从 $x$ 到 $y$ 的有向边。

请你求出，最少需要进行多少次操作，才能使得图满足以下条件：

• 对于任意不同的顶点 $a, b, c$，如果存在从 $a$ 到 $b$ 的有向边，且存在从 $b$ 到 $c$ 的有向边，那么必须存在从 $a$ 到 $c$ 的有向边。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$u_1$ $v_1$
$\vdots$
$u_M$ $v_M$

输出格式

输出答案。

输入输出样例 #1

输入 #1

4 3
2 4
3 1
4 3

输出 #1

3

输入输出样例 #2

输入 #2

292 0

输出 #2

0

输入输出样例 #3

输入 #3

5 8
1 2
2 1
1 3
3 1
1 4
4 1
1 5
5 1

输出 #3

12

说明/提示

限制条件

• $3 \leq N \leq 2000$
• $0 \leq M \leq 2000$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• 如果 $i \neq j$，则 $(u_i, v_i) \neq (u_j, v_j)$
• 所有输入均为整数

样例解释 1

初始时，例如对于顶点 $2, 4, 3$，虽然存在从顶点 $2$ 到顶点 $4$ 的有向边和从顶点 $4$ 到顶点 $3$ 的有向边，但不存在从顶点 $2$ 到顶点 $3$ 的有向边，因此不满足条件。此时，添加如下 $3$ 条有向边后即可满足条件：

• 从顶点 $2$ 到顶点 $3$ 的有向边
• 从顶点 $2$ 到顶点 $1$ 的有向边
• 从顶点 $4$ 到顶点 $1$ 的有向边

另一方面，若少于 $3$ 条边则无法满足条件，因此答案为 $3$。

由 ChatGPT 4.1 翻译