一 亲戚关系

若某个部落过于庞大，则部落成员见面时也有可能不认识。已知某个部落的成员关系图，任意给出其中两个人，判断是否有亲戚关系。规定：1 若 x、y 是亲戚，y 和 z 是亲戚，则 x 和 z 是亲戚；2 若 x、y 是亲戚，则 x 的亲戚也是 y 的亲戚，y 的亲戚也是 x 的亲戚。

如何才能快速判断两个人是否有亲戚关系呢？ 以上规定中，第 1 条是传递关系，第 2 条相对于两个集合的合并，因此对问题可以采用并查集解决。并查集是一种树形结构，用于处理集合的合并及查询问题。

二 算法步骤

1 初始化

将每个节点的集合号都初始化为其自身编号。

2 查找

查找两个元素所在的集合，即找祖宗。查找时，采用递归的方法找其祖宗，找到祖宗时停止；然后回归，回归时将祖宗到当前节点路径上的所有节点都统一为祖宗的集合号。

3 合并

若两个节点的集合号不同，则将两个节点合并为一个集合，合并时只需将一个节点的祖宗号修改为另一个祖宗集合号。只改祖宗即可。

三 图解

假设现在有 7 个人，首先输入亲戚关系图，然后判断两个人是否有亲戚关系。

1 初始化

2 2 和 7 是亲戚关系，查找与合并

3 4 和 5 是亲戚关系，查找与合并

4 3 和 7 是亲戚关系，查找与合并

5 4 和 7 是亲戚关系，查找与合并

6 3 和 4 是亲戚关系，查找与合并

两个元素的集合号相同，无须合并。

7 5 和 7 是亲戚关系，查找与合并

8 5 和 6 是亲戚关系，查找与合并

9 2 和 3 是亲戚关系，查找与合并

两个元素集合号相同，无须合并

10 1 和 2 是亲戚关系，查找与合并