A6557 | 「联合省选 2021 A | B」图函数
来源省选
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
对于一张 $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) + \cdots + f(n, G)$ 的值。
更进一步地，记删除（按输入顺序给出的）第 $1$ 到 $i$ 条边后的图为 $G_i$（$1 \le i \le m$），请你求出所有 $h(G_i)$ 的值。
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) + \cdots + f(n, G)$ 的值。
更进一步地，记删除（按输入顺序给出的）第 $1$ 到 $i$ 条边后的图为 $G_i$（$1 \le i \le m$），请你求出所有 $h(G_i)$ 的值。
输入格式
第一行，两个整数 $n,m$，表示图的点数与边数。
接下来 $m$ 行，每行两个整数，第 $i$ 行的两个整数 $x_i, y_i$ 表示一条有向边 $x_i \to y_i$。
数据保证 $x_i \neq y_i$ 且同一条边不会给出多次。
接下来 $m$ 行，每行两个整数，第 $i$ 行的两个整数 $x_i, y_i$ 表示一条有向边 $x_i \to y_i$。
数据保证 $x_i \neq y_i$ 且同一条边不会给出多次。
输出格式
输出一行 $m + 1$ 个整数，其中第一个数表示给出的完整图 $G$ 的 $h(G)$ 值。第 $i$（$2 \le i \le m + 1$）个整数表示 $h(G_{i-1})$。
输入输出样例
输入 #1
4 6 2 3 3 2 4 1 1 4 2 1 3 1
输出 #1
6 5 5 4 4 4 4
对于所有测试数据：$2 \le n \le {10}^3$，$1 \le m \le 2 \times {10}^5$，$1 \le x_i, y_i \le n$。
每个测试点的具体限制见下表：
| 测试点编号 | $n \le$ | $m\le$ |
|:-:|:-:|:-:|
| $1 \sim 4$ | $10$ | $10 $ |
| $5 \sim 11$ | $100$ | $2 \times {10}^3$ |
| $12 \sim 20$ | ${10}^3$ | $5 \times {10}^3$ |
| $21 \sim 25$ | ${10}^3$ | $2 \times {10}^5$ |
每个测试点的具体限制见下表：
| 测试点编号 | $n \le$ | $m\le$ |
|:-:|:-:|:-:|
| $1 \sim 4$ | $10$ | $10 $ |
| $5 \sim 11$ | $100$ | $2 \times {10}^3$ |
| $12 \sim 20$ | ${10}^3$ | $5 \times {10}^3$ |
| $21 \sim 25$ | ${10}^3$ | $2 \times {10}^5$ |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？