P7520 [省选联考 2021 A 卷] 支配

给定一张 $n$ 个点 $m$ 条边的有向图 $G$，其顶点从 $1$ 到 $n$ 编号。 对于任意两个点 $u, v$，若从顶点 $1$ 出发到达顶点 $v$ 的所有路径都需要经过顶点 $u$，则称顶点 $u$ 支配顶点 $v$。特别地，每个顶点支配其自身。 对于任意一个点 $v$，我们将图中支配顶点 $v$ 的顶点集合称为 $v$ 的受支配集 $D_v$。 现在有 $q$ 次互相独立的询问，每次询问给出一条有向边，请你回答在图 $G$ 中加入该条边后，有多少个顶点的受支配集发生了变化。

无

无

**【样例 #1 解释】** 对于原图，六个点的受支配集分别为：$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 \}$，其他点受支配集不变。 --- **【数据范围】** 对于所有测试数据：$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$ | 无 |