关于并查集的一道题,求思路,n若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系.n规定：x和y是亲戚,y和z是亲

Question

关于并查集的一道题,求思路,
n若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系.
n规定：x和y是亲戚,y和z是亲戚,那么x和z也是亲戚.如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚.
input.txt
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
output.txt
Yes
Yes
No
看了关于并查集的课件,感觉理论都知道,但不知道要怎么用.这题 要怎么构造并查集呢?比如1和5是亲戚,那是1指向5还是5指向1呢,后来又要有1和2是亲戚应该怎么办呢?还有这些人要用什么数据类型来表示呢?感觉了解了一堆理论,但具体实现很困难.

Answer 1

不必关心合并的顺序,因为你只是需要同一家族的人在一个集合里就行了,这样就能保证通过searchfather（i）来求到根节点,只要是一个集合里的元素,同一次查找得到的根节点肯定是相同的,这样就能判断关系了