【统一省选2021 A卷】支配 - 题目

给定一张 $n$ 个点 $m$ 条边的有向图 $G$ ，其顶点从 $1 \sim n$ 编号。

对于任意两个点 $u, v$ ，若从顶点 $1$ 出发到达顶点 $v$ 的所有路径都需要经过顶点 $u$ ，则称顶点 $u$ 支配顶点 $v$ 。特别地，每个顶点支配其自身。

对于任意一个点 $v$ ，我们将图中支配顶点 $v$ 的顶点集合称为 $v$ 的受支配集 $D_{v}$ 。

现在有 $q$ 次互相独立的询问，每次询问给出一条有向边，请你回答在图 $G$ 中加入该条边后，有多少个顶点的受支配集发生了变化。

第一行三个整数 $n, m, q$ ，分别表示图中的顶点数、边数，以及询问数。

接下来 $m$ 行每行两个整数 $x_{i}, y_{i}$ ，表示一条有向边 $x_{i} \to y_{i}$ 。

接下来 $q$ 行每行两个整数 $s_{i}, t_{i}$ ，表示每次询问加入的边 $s_{i} \to t_{i}$ 。

数据保证给出的图 $G$ 中，从 $1$ 号点出发能到达所有其他点，并且图中不包含重边与自环。

对于每个询问输出一行一个整数表示答案。

1
0
2

对于原图，六个点的受支配集分别为： $D_{1} = {1}, D_{2} = {1, 2}, D_{3} = {1, 3}, D_{4} = {1, 3, 4}, D_{5} = {1, 3, 4, 5}, D_{6} = {1, 2, 6}$ 。

加入 $5 \to 6$ 后， $D_{6} = {1, 6}$ ，其他点受支配集不变。

加入 $3 \to 2$ 后没有点受支配集改变。

加入 $2 \to 4$ 后 $D_{4} = {1, 4}, D_{5} = {1, 4, 5}$ ，其他点受支配集不变。

见附加文件中 ex_dominator2.in 与 ex_dominator2.ans。

见附加文件中 ex_dominator3.in 与 ex_dominator3.ans。

对于所有测试数据： $1 \leq n \leq 3000, 1 \leq m \leq 2 \times n, 1 \leq q \leq 2 \times 10^{4}$ 。

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

时间限制： $1 s$

空间限制： $512 MB$

Universal Online Judge