第8章 不相交的集合类型

在这一章，我们将描述不相交的集合类来解决等价性问题。

这种数据结构实现起来很简单。每个例程仅需几行代码，可使用简单的数组。该实现也非常快，每个操作平均需要常数时间。

从理论角度来看，这种数据结构也非常有趣，因为对该数据结构的分析非常难。这种数据结构不存在最坏情形下的函数形式。

本章的主要内容有：

• 展示如何使用最少的代码量来实现不相交的集合类；
• 仅使用两个简单的观察，就可以发现该实现的速度增长极其快；
• 分析一种快速实现的运行时间；
• 了解一种简单的应用。