A6554. 「联合省选 2021 A」支配
编程题
省选/NOI-
知识点
题目描述
给定一张 $n$ 个点 $m$ 条边的有向图 $G$，其顶点从 $1$ 到 $n$ 编号。
对于任意两个点 $u, v$，若从顶点 $1$ 出发到达顶点 $v$ 的所有路径都需要经过顶点 $u$，则称顶点 $u$ 支配顶点 $v$。特别地，每个顶点支配其自身。
对于任意一个点 $v$，我们将图中支配顶点 $v$ 的顶点集合称为 $v$ 的受支配集 $D_v$。
现在有 $q$ 次互相独立的询问，每次询问给出一条有向边，请你回答在图 $G$ 中加入该条边后，有多少个顶点的受支配集发生了变化。
对于任意两个点 $u, v$，若从顶点 $1$ 出发到达顶点 $v$ 的所有路径都需要经过顶点 $u$，则称顶点 $u$ 支配顶点 $v$。特别地，每个顶点支配其自身。
对于任意一个点 $v$，我们将图中支配顶点 $v$ 的顶点集合称为 $v$ 的受支配集 $D_v$。
现在有 $q$ 次互相独立的询问，每次询问给出一条有向边，请你回答在图 $G$ 中加入该条边后，有多少个顶点的受支配集发生了变化。
输入格式
第一行，三个整数 $n, m, q$，分别表示图中的顶点数、边数，以及询问数。
接下来 $m$ 行，每行两个整数 $x_i,y_i$，表示一条有向边从 $x_i$ 到 $y_i$。
接下来 $q$ 行，每行两个整数 $s_i,t_i$，表示每次询问加入的边从 $s_i$ 到 $t_i$。
数据保证给出的图 $G$ 中，从 $1$ 号点出发能到达所有其他点，并且图中不包含重边与自环。
接下来 $m$ 行，每行两个整数 $x_i,y_i$，表示一条有向边从 $x_i$ 到 $y_i$。
接下来 $q$ 行，每行两个整数 $s_i,t_i$，表示每次询问加入的边从 $s_i$ 到 $t_i$。
数据保证给出的图 $G$ 中，从 $1$ 号点出发能到达所有其他点，并且图中不包含重边与自环。
输出格式
对于每个询问，输出一行，一个整数，表示答案。
输入输出样例
输入 #1
6 6 3 1 2 1 3 3 4 4 5 2 6 4 1 5 6 3 2 2 4
输出 #1
1 0 2
说明/提示
对于所有测试数据：$1 \le n \le 3 \times {10}^3$，$1 \le m \le 2 \times n$，$1 \le q \le 2 \times {10}^4$。
每个测试点的具体限制见下表：
| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 2$ | $10$ | 无 |
| $3 \sim 6$ | $100$ | $q \le 100$ |
| $7 \sim 9$ | $1000$ | $m = n - 1$ |
| $10 \sim 15$ | $1000$ | $q \le 2000$ |
| $16 \sim 20$ | $3000$ | 无 |
每个测试点的具体限制见下表：
| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 2$ | $10$ | 无 |
| $3 \sim 6$ | $100$ | $q \le 100$ |
| $7 \sim 9$ | $1000$ | $m = n - 1$ |
| $10 \sim 15$ | $1000$ | $q \le 2000$ |
| $16 \sim 20$ | $3000$ | 无 |