#PQJ478x6141. QOJ 478_6141
QOJ 478_6141
全国青少年信息学奥林匹克竞赛 Day1(A 卷)图函数(graph) 图函数(graph) 【题目描述】 对于一张n 个点m 条边的有向图G(顶点从1 ∼n 编号),定义函数f(u, G):
- 初始化返回值cnt = 0,图G′ = G。
- 从1 至n 按顺序枚举顶点v,如果当前的图G′ 中,从u 到v 与从v 到u 的路 径都存在,则将cnt + 1,并在图G′ 中删去顶点v 以及与它相关的边。
- 第2 步结束后,返回值cnt 即为函数值。 现在给定一张有向图G,请你求出h(G) = f(1, G) + f(2, G) + · · · + f(n, G) 的值。 更进一步地,记删除(按输入顺序给出的)第1 ∼i 条边后的图为Gi(1 ≤i ≤m), 请你求出所有h(Gi) 的值。 【输入格式】 从文件graph.in 中读入数据。 第一行两个整数n, m 表示图的点数与边数。 接下来m 行每行两个整数,第i 行的两个整数xi, yi 表示一条有向边xi →yi。 数据保证xi̸ = yi 且同一条边不会给出多次。 【输出格式】 输出到文件graph.out 中。 输出一行m + 1 个整数,其中第一个数表示给出的完整图G 的h(G) 值。第i (2 ≤i ≤m + 1)个整数表示h(Gi−1)。 【样例1 输入】 1 4 6 2 2 3 3 3 2 4 4 1 5 1 4 6 2 1 7 3 1 【样例1 输出】 1 6 5 5 4 4 4 4 第6 页 共7 页
全国青少年信息学奥林匹克竞赛 Day1(A 卷)图函数(graph) 【样例1 解释】 对于给出的完整图G:
- f(1, G) = 1,过程中删除了顶点1。
- f(2, G) = 1,过程中删除了顶点2。
- f(3, G) = 2,过程中删除了顶点2, 3。
- f(4, G) = 2,过程中删除了顶点1, 4。 【样例2】 见选手目录下的graph/graph2.in 与graph/graph2.ans。 【数据范围】 对于所有测试数据:2 ≤n ≤1000,1 ≤m ≤2 × 105,1 ≤xi, yi ≤n。 每个测试点的具体限制见下表: 测试点编号 n ≤ m ≤ 1 ∼4 10 10 5 ∼11 100 2000 12 ∼20 1000 5000 21 ∼25 2 × 105 第7 页 共7 页