Loading... 我喜欢并查集，实用、可扩展、效率高 --- ## 并查集 1. GET 查询一个元素属于哪个集合 2. Merge 把两个集合合并成一个大集合 以上两种操作是并查集的终极奥义。看似简单，其实往往涉及大量数据的储存和处理，容易超时、超内存。这时就只能用并查集来描述。 看看度娘怎么说： > 并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。 > 并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 看看它的模样：  一个集合看起来像一棵树，并查集就是许多像这样的树组成的森林。 接下来讨论每个集合的具体实现方法。 如果保存每个节点的归属集合，虽然GET时间缩短，但Merge时效率很低，得不偿失。所以一般的方法是以每棵树的根节点作为“代表元素”。 用f数组储存森林，f[i]表示节点i的父节点，特别地，根节点的父节点为本身（为什么不指向0？为了避免合并集合时判断元素是否在同一集合）。这样，每个节点都有唯一的父节点。 有x个元素，起初所以元素各自构成独立集合 ```cpp //初始化 for(int i = 1; i <= n; ++i) f[i] = i; ``` 在查询元素所属集合时，只需不断递归访问当前元素的父节点，直到根节点被找到。  ```cpp //查询元素x所属集合 int get(int x){ if(f[x] == x) return x; return get(f[x]); } ``` 合并两个集合时，令其中一个集合根节点的父节点为另一个集合的根节点（可以指向另一个集合的任意一个节点，但指向根节点查询效率更高，后面要讲）  ```cpp //合并元素x和元素y所在的集合 void merge(int x, int y){ f[get(x)] = get(y); } ``` ### 路径压缩 实际上，我们只关心每个集合的根节点是什么，树的具体形态并不重要。GET的时间长短在于节点x到根节点的距离，所以可以在每次执行GET操作时将访问的节点全部指向根节点。 下面的两棵树是等价的  实现非常简单： ```cpp //查询元素x所属集合 int get(int x){ if(f[x] == x) return x; return f[x] = get(f[x]); } ``` 有意思的是，如下图，当一个集合路径压缩到最优的时候，所有节点的父节点都是根节点，画出来的图形会类似菊花，通常称作菊花图。菊花图在很多~~毒瘤~~图和树问题中十分卡时间，却是并查集集合的最形态。这是由于树是“向下”搜索的，而并查集是“向上”搜索的。即一般图和树保存的是每个节点的子节点，而并查集保存了元素的父节点。  ### 按秩合并 “秩”即集合的大小，按秩合并也称为**启发式合并**，在数据结构相关问题中非常重要，应用广泛。启发式合并的原则是：把小的结构合并到大的结构中，只增加小的结构的查询代价。 在并查集中，合并集合时都把较大集合的根节点作为较小的的集合根节点的父节点。每个集合的大小记录在根节点上。 单独使用路径压缩或按秩合并优化的并查集的复杂度为$O(\log N)$，同时使用两种优化的可以进一步降低至$O(\alpha(N))$。$\alpha(N)$是单变量反阿克曼函数，由于阿克曼函数增长极快，所以$\alpha(N)$可近似一个常数。在一般的题目中，使用路径压缩就够了。 ### 带边权的并查集 用d数组记录每条边的权值，d[x]表示节点x到父节点f[x]之间的边权。 这样，在路径压缩时同时更新访问节点的d值，可以统计每个节点到根节点路径上的一些信息 ... © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
赞
while(1) cout << "666";
可以的，但我没看懂
不错哈，加油哟