1.优秀的算法因为能够解决实际问题而变得更为重要；

2.高效算法的代码也可以很简单；

3.理解某个实现的性能特点是一个挑战；

4.在解决同一个问题的多种算法之间进行选择时，科学方法是一种重要的工具；

5.迭代式改进能够让算法的效率越来越高效；

动态连接：输入是一对整数对的序列，其中每个整数代表某种类型的对象（或触点），我们将整数对p q 解释为意味着p连接到q。我们假设“连接到”是等价关系：

等价关系将对象划分为多个等价类 或连接的组件。等价类称为连通分量或分量。我们的目标是编写一个程序，以从序列中过滤掉多余的对：当程序从输入中读取整数对 p q时，只有在该对点不等价的情况下，才应将对写入到输出中，并且将p连接到q。如果等价，则程序应忽略整数对pq 并继续读取下对。

 动态连通性问题的应用：

在更高的抽象层次上，可以将输入的所有整数看做属于不同的数学集合。

设计算法的第一个任务就是精确地定义问题。

算法解决的问题越大，它完成任务所需的时间和空间可能越多。我们不可能预先知道这其间的量化关系，通常只会在发现解决问题很困难，或是代价巨大，或是发现算法所提供的信息比原问题所需要的更加有用时修改问题。例如，连通性问题只要求我们的程序能够判断出给定的整数对是否相连，但并没有要求给出两者之间的通路上的所有连接。这样的要求更难，并会得出另一组不同的算法。

为了定义和说明问题，先设计一份API 来封装基本操作: 初始化，连接两个触点，查找某个触点的分量 ，判断两个触点是否属于同一分量，分量的数量：

为解决动态连通性问题设计算法的任务转化为实现这份API：

数据结构的性质会直接影响算法的效率。这里，以触点为索引，触点和连接分量都是用 int 值表示，将会使用分量中某个触点的值作为分量的标识符。所以，一开始，每个触点都是只含有自己的分量，分量标识符为触点的值。由此，可以初步实现一部分方法：

Union-find 的成本模型 是数组的访问次数(无论读写)。

quick-find 算法是保证当且仅当 id[p] 等于 id[q] 时，p 和 q 是连通的。也就是说，在同一个连通分量中的所有触点在 id[ ] 中的值全部相等。

所以Find 方法只需返回id[q]，Union 方法需要先判断Find(p) 是否等于Find(q) ,若相等直接返回；若不相等，需要将 q 所在的连通分量中所有触点的 id [ ] 值全部更新为 id[p]。