#P1288. 是不是亲戚

是不是亲戚

Description

若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

规定:x 和 y 是亲戚,y 和 z 是亲戚,那么 x 和 z 也是亲戚。如果 x,y 是亲戚,那么 x 的亲戚都是 y 的亲戚,y 的亲戚也都是 x 的亲戚。

Input Format

输入由两部分组成。

  第一部分以NM开始。N为问题涉及的人的个数(1<=N<=20000)。这些人的编号为1,2,3,…, N。下面有M(1<= M <= 1 000 000),每行有两个数ai, bi,表示已知aibi是亲戚。

  第二部分以Q开始。以下Q行有Q个询问(1<=Q<=1 000 000),每行为ci, di,表示询问cidi是否为亲戚。

<math xm<math xm<math xm<math xm

Output Format

P行,每行一个 Yes 或 No。表示第 <math xmlns="http://www.w3.org/1998/Math/MathML">i 个询问的答案为“具有”或“不具有”亲戚关系。
6 5
1 2
1 5
3 4
5 2
1 3
3
1 4
2 3
5 6
Yes
Yes
No

Source

并查集