灵鹊做题网关于并查集的一道题,求思路,
来源：学生作业帮 编辑：灵鹊做题网作业帮 分类：数学作业 时间：2024/05/16 18:04:15
关于并查集的一道题,求思路,
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是亲戚应该怎么办呢?还有这些人要用什么数据类型来表示呢?感觉了解了一堆理论,但具体实现很困难.
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是亲戚应该怎么办呢?还有这些人要用什么数据类型来表示呢?感觉了解了一堆理论,但具体实现很困难.
不必关心合并的顺序,因为你只是需要同一家族的人在一个集合里就行了,这样就能保证通过searchfather（i）来求到根节点,只要是一个集合里的元素,同一次查找得到的根节点肯定是相同的,这样就能判断关系了
再问： 没很懂，这个根节点怎么定呢？我问了一下同学，说是初始时自己对应自己，后来每输入两个数，就把他们的father值设置成一样，也就是大家都指向一个集合里第一个输入的那个人了，这样可以做但感觉和老师讲得不一样，你是一样想法还是其他方法呢？
再答： 没有必要追究根节点是谁，每一次合并只是相当于为这个集合确定了一个唯一的根节点，这个根节点在多次合并中是可以变化的，只要保证在查询的时候同一个集合中的元素指向的是同一个节点就行，至于指向的到底是集合中的那一个元素并不重要，你可以单步跟踪看一下查询时个集合根节点的情况
再问： 没很懂，这个根节点怎么定呢？我问了一下同学，说是初始时自己对应自己，后来每输入两个数，就把他们的father值设置成一样，也就是大家都指向一个集合里第一个输入的那个人了，这样可以做但感觉和老师讲得不一样，你是一样想法还是其他方法呢？
再答： 没有必要追究根节点是谁，每一次合并只是相当于为这个集合确定了一个唯一的根节点，这个根节点在多次合并中是可以变化的，只要保证在查询的时候同一个集合中的元素指向的是同一个节点就行，至于指向的到底是集合中的那一个元素并不重要，你可以单步跟踪看一下查询时个集合根节点的情况