临时封路

普及+/提高 周赛 CSP-S 并查集 离线处理 连通性

题目描述

一座城市有 $n$ 个路口和 $m$ 条双向道路。第 $i$ 条道路连接路口 $u_i$ 与 $v_i$。

接下来会发生 $q$ 条事件:

  • D x:编号为 $x$ 的道路被临时封闭。保证同一条道路最多被封闭一次。

  • Q u v:询问在当前未封闭道路组成的图中,路口 $u$ 与路口 $v$ 是否连通。

请按照询问出现的顺序输出答案。

输入格式

第一行三个整数 $n,m,q$。

接下来 $m$ 行,第 $i$ 行两个整数 $u_i,v_i$,表示第 $i$ 条道路连接的两个路口。

接下来 $q$ 行,每行表示一条事件,格式为 D xQ u v

输出格式

对于每个询问,输出一行 YesNo。若两个路口连通,输出 Yes;否则输出 No

数据范围

$1 \le n \le 2\cdot 10^5$。

$1 \le m,q \le 2\cdot 10^5$。

$1 \le u_i,v_i \le n$。

$1 \le x \le m$。

$1 \le u,v \le n$。

样例输入 1

4 3 5
1 2
2 3
3 4
Q 1 4
D 2
Q 1 4
D 1
Q 1 2

样例输出 1

Yes
No
No
时间限制: 1000ms
内存限制: 256MB
通过率: 0.0%
提交数: 0

设置

导航栏小工具

时钟
显示实时时钟(默认组件)
📝
代码粘贴板
快速创建和分享代码片段