首页 > 试题广场 >

小美的朋友关系

[编程题]小美的朋友关系
  • 热度指数:307 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小美认为,在人际交往中,但是随着时间的流逝,朋友的关系也是会慢慢变淡的,最终朋友关系就淡忘了。
现在初始有一些朋友关系,存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中,某两人是否可以通过朋友介绍互相认识?
事件共有 2 种:
1 u v:代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v:代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注:介绍可以有多层,比如 2 号把 1 号介绍给 3 号,然后 3 号再把 1 号介绍给 4 号,这样 1 号和 4 号就认识了。

输入描述:
第一行输入三个正整数n,m,q,代表总人数,初始的朋友关系数量,发生的事件数量。
接下来的m行,每行输入两个正整数u,v,代表初始编号u的人和编号v的人是朋友关系。
接下来的q行,每行输入三个正整数op,u,v,含义如题目描述所述。
1\leq n \leq 10^9
1\leq m,q \leq 10^5
1\leq u,v \leq n
1\leq op \leq 2
保证至少存在一次查询操作。


输出描述:
对于每次 2 号操作,输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识,则输出"Yes"。否则输出"No"。
示例1

输入

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

输出

Yes
No
No

说明

第一次事件,1 号和 5 号本来就不是朋友,所以无事发生。
第二次事件是询问,1 号和 3 号可以通过 2 号的介绍认识。
第三次事件是询问,显然 1 号和 4 号无法互相认识。
第四次事件,1 号和 2 号淡忘了。
第五次事件,此时 1 号无法再经过 2 号和 3 号互相认识了。
卡在第27/30个算例不知道怎么回事
编辑于 2024-03-22 16:23:23 回复(0)