c++高级数据结构之并查集

一.相关原理1.概念首先我们得明晰并查集在图形层面是什么——一片森林也就是很多个不相交的集合(很多棵树)。2.表示方式像堆那样用数组存储每一个人:一开始给这些学生编好号数组下标就是他们对应的编号。一段时间后大家熟络组成不同小群体编号012的同学担任队长这些同学间产生了联系。以上的三棵树就可以说是一个并查集(森林)。这是形成森林后的存储情况。结论:注:一开始的数组中数组元素要均为-1。因此存储用的是双亲表示法数组中的元素可根据正负区分出谁是父亲谁是孩子。数组元素为负数负号代表父节点其绝对值代表整棵树(集合)节点的数量数组元素为非负数代表子节点且元素的值代表该子节点所在树的根节点的下标。数组下标表示每个节点的编号。3.如何合并两棵树需要去合并两棵树的根节点在存储中的操作以下图为例1合并到0上就是将1对应的值-3加给0对应的值-4随后1对应的值变成0此刻的1不再是大哥转而做了0的小弟。合并后的示意图:二.并查集的实现在理解实现之前如果对map的重载[]不太熟悉的读者可参考笔者这篇文章cpp数据结构之map1.给人名建立人与编号的映射关系代码:#pragma once #includemap//利用map和set做到根据编号找人人找编号的映射关系。 #includevector templateclass T class UnionFindSet { public: UnionFindSet(const T* a, size_t n) { for (int i 0; i n; i) { _a.push_back(a[i]);//将姓名导入vector _indexMap[a[i]] i;//map的[]的特性——给key,返回value,还有插入的功能由此可在map中做映射 } } private: vectorT _a;//数组下标就是名字的编号根据编号找人 mapT, int _indexMap;//利用map,根据人找编号 };测试用例:#includeiostream using namespace std; #includeUnionFindSet.h int main() { string a[] { 张三,李四,王五,赵六 }; UnionFindSetstring ufs(a, 4); return 0; }结果:2.不建立映射关系直接编好号的并查集的实现①.寻根(最核心)//寻根 int FindRoot(int x) { int root x; while (_ufs[root] 0) { root _ufs[root]; } return root; }root一直往上跳不断寻找父节点直到root对应的数组元素为负数便找到了根节点。②.合并//合并 void Union(int x1, int x2) { int root1 FindRoot(x1); int root2 FindRoot(x2); if (root1 root2) { return; } if (root1 root2) { swap(root1,root2);//保证小的节点去做根 } //将root2合并给root1 _ufs[root1] _ufs[root2]; _ufs[root2] root1;//root1开始当小弟它的父节点是root2 }③.是否在同一集合(同一棵树)里bool InSet(int x1, int x2) { return FindRoot(x1) FindRoot(x2); }④.统计集合个数由于数组里的元素为负数就代表这是一个根,只要统计负数的个数就能知道集合的个数。size_t SetSize() { size_t size 0; for (size_t i 0; i _ufs.size(); i) { if (_ufs[i] 0) { size; } } return size; }