使用树来表示集合。树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表。 a b d c e f g 并查集的树表示 4 树的节点表示集合中的元素，指针表示指向父节点的指针，根节点的指针指向自己，表示没有父节点。沿着每个节点的父节点指针不断向上查找，最终就可以找到该树的跟节点，即集合的代表元素。 所以，并查集的初始化就是构造出一个森林，每个元素自身是一个集合。： b c e d a 并查集的初始化 路径压缩 和所有树形结构一样，并查集也会发生退化，复杂度也随这退化而变得很高。使得并查集的查询效率大大下降， 并查集的退化 2 7 4 1 这时，每查询一个值，都需要遍历整棵树才能找到集合的代表元素，使得使用并查集的意义不大。尤其在需要多次查询的情况下，退化使每次查询做了大量的重复工作，浪费了大量的时间。 5 为了防止退化的发生，可以通过记录每课树的高度，合并时总是从高度小的向高度大的连边。如下图： １ ４ ２ ６ ５ ３ 路径压缩１ ２ ４ １ ３ ６ ５ 对于每个节点，一旦向上走到了一次跟节点，就把这个点到父亲的边改为直接连向根。 而且，在此只上，在查询过程中向上查询经过的所有顶点，都可以改为直接连到根节点，这样再次查询这些节点时，就可以直接查询到根节点。 ２ １ ３ ４ １ ２ ３ ４ 路径压缩２ 优化后并查集的平均复杂度为Ｏ(α(n))。 6 算法描述 分别设计union_search_set类实现并查集和kruskal类实现KRUSKAL算法求最小生成树。 union_search_set类的设计 union_search_set类的成员函数
成员函数名称 接受参数 返回值类型 功能描述 union_search_set 初始化元素个数 void 初始化并查集 find 集合中一个元素 int 查找该元素的根节点 unite 两个不同集合的元素 void 将两个元素所在集合合并 same 集合中一个元素 bool 判断两个元素是否位于同一集合中 在union_search_set类中用编号代表每个元素。数组par表示的是父亲的编号，当par[x]==x时，x是所在的树的根。所以，应将par中的所以元素初始化为其下标。而find也只需不断向上查找，直到par[x]==x。代码如下： int find(int x){ if (par[x]== x) return x; else return par[x] = find(par[x]);} same函数只要调用find函数判断两个元素的根节点是否相同即可。代码: bool same(int x, int y){ return find(x) == find(y); } unite函数通过rank[]数组记录树的高度，根据高度决定连边的方式，防止并查集发生退化，代码如下： void unite(int x, int y){ x = find(x); y = find(y);
