#PQJ477x6144. QOJ 477_6144

    ID: 2996 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:NOI 2021 统一省选并查集

QOJ 477_6144

全国青少年信息学奥林匹克竞赛 Day2(A 卷)支配(dominator) 支配(dominator) 【题目描述】 给定一张n 个点m 条边的有向图G,其顶点从1 ∼n 编号。 对于任意两个点u, v,若从顶点1 出发到达顶点v 的所有路径都需要经过顶点u, 则称顶点u 支配顶点v。特别地,每个顶点支配其自身。 对于任意一个点v,我们将图中支配顶点v 的顶点集合称为v 的受支配集Dv。 现在有q 次互相独立的询问,每次询问给出一条有向边,请你回答在图G 中加入 该条边后,有多少个顶点的受支配集发生了变化。 【输入格式】 从文件dominator.in 中读入数据。 第一行三个整数n, m, q,分别表示图中的顶点数、边数,以及询问数。 接下来m 行每行两个整数xi,yi,表示一条有向边xi →yi。 接下来q 行每行两个整数si,ti,表示每次询问加入的边si →ti。 数据保证给出的图G 中,从1 号点出发能到达所有其他点,并且图中不包含重边 与自环。 【输出格式】 输出到文件dominator.out 中。 对于每个询问输出一行一个整数表示答案。 【样例1 输入】 1 6 6 3 2 1 2 3 1 3 4 3 4 5 4 5 6 2 6 7 4 1 8 5 6 9 3 2 10 2 4 第6 页 共7 页

全国青少年信息学奥林匹克竞赛 Day2(A 卷)支配(dominator) 【样例1 输出】 1 1 2 0 3 2 【样例1 解释】 对于原图,六个点的受支配集分别为:D1 = {1},D2 = {1, 2},D3 = {1, 3},D4 = {1, 3, 4},D5 = {1, 3, 4, 5},D6 = {1, 2, 6}。 加入5 →6 后,D6 = {1, 6},其他点受支配集不变。 加入3 →2 后没有点受支配集改变。 加入2 →4 后D4 = {1, 4},D5 = {1, 4, 5},其他点受支配集不变。 【样例2】 见选手目录下的dominator/dominator2.in 与dominator/dominator2.ans。 【样例3】 见选手目录下的dominator/dominator3.in 与dominator/dominator3.ans。 【数据范围】 对于所有测试数据:1 ≤n ≤3000,1 ≤m ≤2 × n,1 ≤q ≤2 × 104。 每个测试点的具体限制见下表: 测试点编号 n ≤ 特殊性质 1 ∼2 10 无 3 ∼6 100 q ≤100 7 ∼9 1000 m = n −1 10 ∼15 q ≤2000 16 ∼20 3000 无 第7 页 共7 页