信息学奥赛中的特殊数据结构——并查集在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1〜3 秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构一一并查集来描述。一、数学准备首先，我们从数学的角度给出等价关系和等价类的定义：定义 1：如果集合 S 中的关系 R 是自反的，对称的，传递的，则称他为一个等价关系。自反：x=x；对称：若 x=y，贝 iy=x；传递：若 x=y、y=z，贝 ix=zo要求：x、y、z 必须要同一个子集中。定义 2：如果 R 是集合 S 的等价关系。对于任何 x^S，由[x]R={y|yWSandxRy}给出的集合[x]R 匸 S 称为由 xWS 生成的一个 R 的等价类。定义 3：若 R 是集合 S 上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以按 R 将 S 划分为若干不相交的子集 S,S,S,S,……，他们的并即为 S，则这1234些子集 S 变称为 S 的 R 等价类。i划分等价类的问题的提法是：要求对 S 作出符合某些等价性条件的等价类的划分，已知集合 S 及一系列的形如“x 等价于 y”的具体条件，要求给出 S 的等价类的划分，符合所列等价性的条件。（我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合 S 划分成 n 个联系的子集，然后再判断 x，y 是否在一个联系子集中。）二、引题亲戚（relation）【问题描述】若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：X 和 y 是亲戚，y 和 z 是亲戚，那么 X 和 z 也是亲戚。如果 x,y 是亲戚，那么 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。（人数 W5000,亲戚关系＜5000，询问亲戚关系次数＜5000）。【算法分析】1.算法 1，构造图论模型。用一个 n*n 的二维数组描述上面的图形，记忆各个点之间的关系。然后，只要判断给定的两个点是否连通则可知两个元素是否有“亲戚”关系。但要实现上述算法，我们遇到两个困难：(1...
