(排序先欠着)
1.不相交集类
适用于快速判断等价关系。
初始化:一些元素,它们互相之间没有关系,只和自己有关系。
操作:查找:输入一个元素,返回它所在的等价类。
求并:输入两个元素,将它们的等价类合并。
查找和求并不能同时都为,但是可以分别为。
实现方法:用树来表示每个等价类,两个等价类合并就是把一个等价类的根节点连接到另一个等价类上,查找就是遍历每一棵树,用数组容易实现。
一次操作的时间复杂度:。
优化:利用等价关系的传递性,让x到根的每个结点的父节点都变成根结点。经过复杂的数学推导,可以证明此时一次操作的时间复杂度为:。
例题:洛谷P3367