题目详情题解（0）讨论（0）提交记录（0）

AT_abc435_d.[ABC435D] Reachability Query 2

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你一个有向图，包含 NN 个顶点和 MM 条边。
顶点编号为 11 到 NN，第 ii 条边是从顶点 XiX_i 指向顶点 YiY_i 的有向边。
初始时，所有顶点都是白色。

请依次处理 QQ 个查询。每个查询有如下两种类型之一：

  • 1 v：将顶点 vv 染成黑色。
  • 2 v：判断是否存在一条路径，可以从顶点 vv 沿边行走到某个黑色顶点。

输入格式

输入从标准输入读取，格式如下：

N MN\ M
X1 Y1X_1\ Y_1
⋮\vdots
XM YMX_M\ Y_M
QQ
query1\mathrm{query}_1
⋮\vdots
queryQ\mathrm{query}_Q

queryi\mathrm{query}_i 表示第 ii 个查询，具体格式如下：

1 v1\ v

或

2 v2\ v

输出格式

设共有 qq 个第二种类型的查询。输出 qq 行。

对于第 ii 个第二种类型的查询，如果能够从顶点 vv 沿边到达某个黑色顶点，输出 Yes，否则输出 No。

输入输出样例

  • 输入#1

    5 6
1 2
2 3
3 1
4 5
1 4
2 5
5
1 3
2 1
2 4
1 5
2 4

    输出#1

    Yes
No
Yes

说明/提示

样例解释 1

  • 初始时，给定图如下最左侧图所示。
  • 第一个查询后，顶点 33 被染成黑色，如中间所示。
  • 对第二个查询，可以从顶点 11 沿路径到达黑色顶点 33。
  • 第三个查询，从顶点 44 无法到达任何黑色顶点。
  • 第四个查询后，顶点 55 被染成黑色，如最右侧所示。
  • 第五个查询，从顶点 44 开始可以到达黑色顶点 55。

图示

数据范围

  • 1≤N≤3×1051 \leq N \leq 3 \times 10^5
  • 0≤M≤3×1050 \leq M \leq 3 \times 10^5
  • 1≤Q≤3×1051 \leq Q \leq 3 \times 10^5
  • 1≤Xi,Yi≤N1 \leq X_i, Y_i \leq N
  • 不存在自环，即 Xi≠YiX_i \neq Y_i。
  • 不存在重边，即 (Xi,Yi)(X_i, Y_i) 互不相同。
  • 查询中的 1≤v≤N1 \leq v \leq N。
  • 所有输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页