【C++数据结构】并查集的路径压缩

文章目录

前言

以往出过一期并查集的简单入门：
一篇文章了解并查集

路径压缩

路径压缩实际上是在数据量太大的时候，访问一些数据可能在位于叶子位置，导致访问的效率不高，这个时候有两种方法进行提高效率：

• 两颗树合并的时候，节点少的树往节点多的树合并。目的：为了使节点层数增多的节点相对减少。
• 查找的时候对该路径上的节点进行路径压缩。 目的：使更多的节点在第二层。 最好不要用递归的时候进行路径压缩，因为路径深可能导致栈溢出。 若在上图查找1，我们查找完之后图应该变为下面这样： 即1，2，3，8的处的索引都指向0（父亲），这样就进行了压缩，并且查找的时候本身就会去找根，所以开销不是很大。while (_unionset[cur] >= 0)到0这个点的时候存储的就是负数，就会结束了。

FindRoot函数进行压缩，Union进行小树合并到大树。

#include<iostream>#include<vector>#include<map>using std::map;using std::vector;//并查集是一个森林，一开始数组全部初始化为-1，代表每个人都是一颗独立的子树//然后开始合并（PutInRange）,合并可以提供两个版本，一种是用编号进行合并，一种是用数值进行合并classUnionFindSet{private:
    vector<int> _unionset;public:UnionFindSet(size_t n):_unionset(n,-1){}intFindRoot(int cur){//找跟，是比较重要的环节int root = cur;while(_unionset[root]>=0){//根节点的值一定是负数
            root = _unionset[root];}//若数据量大，可以加上以下的压缩函数//合并的时候，该路径的所有节点都可以被合并while(_unionset[cur]>=0){//若更改当前位置的父亲节点，会丢失以前的父亲节点int pIndex = _unionset[cur];
            _unionset[cur]= root;
            cur = pIndex;}return root;}voidUnion(constint& index1,constint& index2){int root1 =FindRoot(index1);int root2 =FindRoot(index2);//有可能两个树是在一颗树当中，此时倘若合并会出错if(root1 == root2)return;//这里可以小的合并给大的，因为层次深的节点就少了if(_unionset[root1]> _unionset[root2]){swap(root1, root2);}//相当于root1所在位置的节点更多，root2也变成了root1所在的一颗子树
        _unionset[root1]+= _unionset[root2];
        _unionset[root2]= root1;}boolTestUnionSet(constint& v1,constint& v2){int root1 =FindRoot(v1);int root2 =FindRoot(v2);//有可能两个树是在一颗树当中，此时倘若合并会出错if(root1 == root2)true;returnfalse;}};

结束了~

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论