第六章不相交集

文章目录

等价关系

等价关系是满足以下三条性质的关系：(1)自反性；(2)对称性；(3)传递性。

对一个集合S，a是S中的一个元素，a的等价类是所有与a等价的元素组成的集合；等价类形成对集合S的一个划分；因此，要确定两个元素是否等价，只需要判断它们是否在一个等价类中。

在集合S上有两种运算：(1)Find：找出一个元素所在等价类；(2)Union：将两个等价类合并；

要表示一个等价类，可使用树，两个相同的元素在同一棵树上，因此有同一个根节点，将根节点作为此等价类的标识；此时只需要每个节点的父节点信息，因此只需使用一个数组P存储每个节点的父节点，而根节点的父节点置0。

对于Find运算，一直索引到根节点即可(判断根节点即P[x]是否为0)；

对于Union运算，将一个树的根节点指向另一棵树的根节点即可；

若随机地挂接树会导致出现一些很坏的情形；为此，在挂接时，考察树的节点个数，将节点少的树挂接到节点多的树上；因此，需要记录一个树的节点个数，这可以记录在根节点，将树的节点个数的相反数置为根节点的P[x]。

为使Find运算更快，使用路径压缩：在寻找一个元素的等价类时，将其遍历的节点的父节点均置为根节点，这可以极大地降低下次Find的代价。