Skip to content

1340: Strongly connected

题目

题目描述

给定一张 $n$ 个点,$m$ 条边的有向图,询问有多少对点 $(u, v)$ 满足:

  1. 存在一条从 $u$ 到 $v$ 的路径;
  2. 存在一条从 $v$ 到 $u$ 的路径;
  3. $u < v$。

Input

请从 stdin 读入。

输入第一行为两个个正整数 $n, m(1 \leq n, m \leq 10^5)$。

接下来 $m$ 行,第 $i$ 行为用空格隔开的整数 $u_i, v_i (1 \leq u_i, v_i \leq n)$,表示第 $i$ 条边为从 $u_i$ 到 $v_i$。

输入可能存在重边与自环。

对于 $ 30$ 分的数据,$n \leq 500$。

Output

请输出到 stdout 中。

输出一行,包含一个整数,表示你的答案。

Sample Input

txt 4 4 1 2 2 3 3 4 4 1

txt 4 4 1 2 2 3 3 4 1 4

txt 4 4 1 1 2 3 2 3 3 2

Sample Output

txt 6

txt 0

txt 1

Constraints

Time Limit: 1s

Memory Limit: 128MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!