UOJ Logo Universal Online Judge

UOJ

#626. 【统一省选2021 A/B卷】图函数

统计

对于一张 $n$ 个点 $m$ 条边的有向图 $G$ (顶点从 $1 \sim n$ 编号),定义函数 $f(u, G)$ :

  1. 初始化返回值 $cnt = 0$,图 $G′ = G$。
  2. 从 $1$ 至 $n$ 按顺序枚举顶点 $v$,如果当前的图 $G′$ 中,从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在,则将 $cnt + 1$,并在图 $G′$ 中删去顶点 $v$ 以及与它相关的边。
  3. 第 $2$ 步结束后,返回值 $cnt$ 即为函数值。

现在给定一张有向图 G,请你求出 $h(G) = f(1, G) + f(2, G) + \dots + f(n, G)$ 的值。

更进一步地,记删除(按输入顺序给出的)第 $1 \sim i$ 条边后的图为 $G_i (1 \leq i \leq m)$,请你求出所有 $h(G_i)$ 的值。

输入格式

第一行两个整数 $n, m$ 表示图的点数与边数。

接下来 $m$ 行每行两个整数,第 $i$ 行的两个整数 $x_i, y_i$ 表示一条有向边 $x_i \rightarrow y_i$。

数据保证 $x_i \neq y_i$ 且同一条边不会给出多次。

输出格式

输出一行 $m + 1$ 个整数,其中第一个数表示给出的完整图 $G$ 的 $h(G)$ 值。第 $i (2 \leq i \leq m + 1)$ 个整数表示 $h(G_{i-1})$。

样例一

input

4 6
2 3
3 2
4 1
1 4
2 1
3 1

output

6 5 5 4 4 4 4

explanation

对于给出的完整图 $G$:

  1. $f (1, G) = 1$,过程中删除了顶点 $1$。
  2. $f (2, G) = 1$,过程中删除了顶点 $2$。
  3. $f (3, G) = 2$,过程中删除了顶点 $2, 3$。
  4. $f (4, G) = 2$,过程中删除了顶点 $1, 4$。

样例二

见附加文件中 ex_graph2.inex_graph2.ans

限制与约定

对于所有测试数据:$2 \leq n \leq 1000, 1 \leq m \leq 2 \times 10^5, 1 \leq x_i, y_i \leq n$。

每个测试点的具体限制见下表:

测试点编号 $n \leq$ $m \leq$
$1 \sim 4$ $10$ $10$
$5 \sim 11$ $100$ $2000$
$12 \sim 20$ $1000$ $5000$
$21 \sim 25$ $2 \times 10^5$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载