1278. 家族

时间限制 1000 ms   内存限制 128 MB

若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规定:$x$和$y$是亲戚,$y$和$z$是亲戚,那么$x$和z也是亲戚。如果$x,y$是亲戚,那么$x$的亲戚都是$y$的亲戚,$y$的亲戚也都是$x$的亲戚。

输入数据

第一行:三个整数$n,m,p,(n\le 5000,m\le 5000,p\le 5000)$,分别表示有$n$个人,$m$个亲戚关系,询问$p$对亲戚关系。
以下$m$行:每行两个数$M_i,M_j,1\le M_i,M_j\le N$,表示$A_i$和$B_i$具有亲戚关系。
接下来$p$行:每行两个数$P_i,P_j$,询问$P_i$和$P_j$是否具有亲戚关系。

输出数据

输出$p$行,每行一个YesNo。表示第$i$个询问的答案为“具有”或“不具有”亲戚关系。

样例输入

复制
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6 · · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n

样例输出

复制
Yes
Yes
No   \n
   \n
  \n

提交

请先 登录

Source

cdwind整理提交

© 2026 FAQs Contact About