← 返回题目列表

AtCoder · abc420_e

H. 可达性查询

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

给你一个无向图 N 顶点和零边。
顶点已编号 1,2,\dots,N,最初所有顶点都是白色的。
进程总共 Q 以下三种类型的查询:

  • 类型 1 :添加连接顶点的无向边 u 和 v.
  • 类型 2 :如果顶点 v 为白色,将其改为黑色;如果是黑色,请将其更改为白色。
  • 类型 3 :判断从顶点是否可以到达黑色顶点 v 通过遍历零个或多个边;报告 Yes 如果可以到达,并且 No 否则。

约束

  • 所有输入值均为整数。
  • 1 \le N \le 2 \times 10^5
  • 1 \le Q \le 6 \times 10^5
  • 类型 1 查询满足以下约束:
    • 1 \le u < v \le N
    • 对于每个查询,没有边连接 u 和 v 已添加到该查询之前。
  • 类型 2,3 查询满足以下约束:
    • 1 \le v \le N

输入

输入由标准输入按以下格式给出:

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

其中 \rm{Query}_i 代表 i第一个查询。

类型 1 查询按以下格式给出:

1 u v

类型 2 查询按以下格式给出:

2 v

类型 3 查询按以下格式给出:

3 v

输出

对于每种类型 3 查询,输出答案如下:

  • Yes 如果从顶点可以到达黑色顶点 v 通过遍历零个或多个边;
  • No 如果从顶点无法到达黑色顶点 v 通过遍历零个或多个边。

示例输入 1

5 12
3 2
2 2
3 2
1 2 5
1 3 4
3 4
3 5
1 4 5
1 1 3
3 1
2 2
3 1

示例输出 1

No
Yes
No
Yes
Yes
No

在此输入中,图最初有五个顶点和零个边。
该输入包含 12 查询。

  • 第一个查询是 3 2.
    • 此时从顶点无法到达黑色顶点 2 通过遍历零个或多个边,因此报告 No.
  • 第二个查询是 2 2.
    • 顶点 2 是白色的,所以将其更改为黑色。
  • 第三个查询是 3 2.
    • 此时黑色顶点 2 可以从顶点到达 2 通过遍历零个或多个边。因此,报告 Yes.
  • 第四个查询是 1 2 5.
    • 添加连接顶点的边 2,5.
  • 第 5 个查询是 1 3 4.
    • 添加连接顶点的边 3,4.
  • 第 6 个查询是 3 4.
    • 此时从顶点无法到达黑色顶点 4 通过遍历零个或多个边,因此报告 No.
  • 第 7 个查询是 3 5.
    • 此时黑色顶点 2 可以从顶点到达 5 通过遍历零个或多个边。因此,报告 Yes.
  • 第 8 个查询是 1 4 5.
    • 添加连接顶点的边 4,5.
  • 第 9 个查询是 1 1 3.
    • 添加连接顶点的边 1,3.
  • 第 10 个查询是 3 1.
    • 此时黑色顶点 2 可以从顶点到达 1 通过遍历零个或多个边。因此,报告 Yes.
  • 第 11 个查询是 2 2.
    • 顶点 2 是黑色的,所以将其更改为白色。
  • 第 12 个查询是 3 1.
    • 此时从顶点无法到达黑色顶点 1 通过遍历零个或多个边,因此报告 No.