[数据结构]并查集--C++版本的实现代码

并查集的基本框架

查找一个元素在哪一个集合

判断两个元素是否在同一个集合

将两个集合进行合并

查询有多少组

测试

大学班级的同学会来自于五湖四海，每个人的家乡可能都不相同，那么如何将相同省份的同学连接到一块，也就是按省份进行分组呢？并查集就可以很好的解决该问题，并查集是一个森林，他内部的每一棵多叉树，都是一个按照特定条件划分出来的相同属性的集合。

并查集的基本框架

并查集是使用数组的形式去表示森林的结构，森林中的每一颗树的每一个节点，采用的是双亲指针法，也就是说每一个节点，只能找到他的父节点，没法向下找子节点。每个存储的元素会被映射为一个下标序号，数组的值，存放的是他的父节点的下标。例如a[i] = n；那么就代表序号为i的元素的父节点是序号为n的元素。

所以说除了维护一个并查集数组之外，还要维护一个哈希map来进行字符串转下标的结构，和一个数组用来进行下标转字符串的操作。如果说数据本身就是数字的话，那就没必要了。

初始化的时候，设置为-1，是因为首先让每一个元素都是一个特定的集合，然后根据情况，调用方法逐步的进行元素的合并操作，来完成并查集的构建操作。

class UnionFind
{
private:std::vector<int> _uf;									//并查集数组std::unordered_map<std::string, int> _stringToMap;		//string类型转下标std::vector<std::string> _mapToString;					//下标转string类型public://初始化UnionFind(int n, std::vector<std::string>& strs): _uf(n, -1), _mapToString(n){for (int i = 0; i < n; i++){_stringToMap[strs[i]] = i;_mapToString[i] = strs[i];}}
};

查找一个元素在哪一个集合

采用循环的方式，一直追溯到根节点的为止，每一个数组元素都记录着父节点的下标为止，如果说该数组元素是一个负数的话，那么就代表这个数组元素是根节点。

//查看元素在哪个集合中
int Find(int val)
{//如果查找的下标，超出了数组范围if (val >= _uf.size()){return -1;}//一直查找到根节点while (_uf[val] >= 0){int parent = _uf[val];val = parent;}return val;
}
//按string类型进行查找 
const std::string& Find(const std::string& val)
{//查找映射关系auto it = _stringToMap.find(val);//没找到--返回空字符串if (it == _stringToMap.end()){return std::string("");}int index = Find((*it).second);return _mapToString[index];
}

判断两个元素是否在同一个集合

判断两个元素是否在同一个集合，也就是判断两个元素的跟节点是不是一样的即可，所以复用Find函数代码。

    //判断两个元素是否在同一个集合bool IsSame(int val1, int val2){return Find(val1) == Find(val2);}//按string类型的判断bool IsSame(const std::string& str1, const std::string& str2){return Find(str1) == Find(str2);}

将两个集合进行合并

	//将两个集合进行合并void UnionSet(int val1, int val2){//先查找两个元素的根节点int root1 = Find(val1);int root2 = Find(val2);//如果一样，就不用合并了if (root1 == root2)return;//将小的集合合并到大的集合当中if (std::abs(_uf[root1]) < std::abs(_uf[root2])){std::swap(root1, root2);}//更新数组值与下标_uf[root1] += _uf[root2];_uf[root2] = root1;}

查询有多少组

	//查询有多少组int CountSet(){int count = 0;for (auto num : _uf){if (num < 0)count++;}return count;}

测试

#include "UnionFind.hpp"int main()
{std::vector<std::string> classmates = {"林晓", "陈悦", "刘阳", "张宇", "王婷","李辉", "赵静", "孙峰", "周瑶", "吴俊"};//创建并查集UnionFind unionfind(10, classmates);//进行分组操作unionfind.UnionSet(0, 1);unionfind.UnionSet(0, 3);unionfind.UnionSet(2, 4);unionfind.UnionSet(2, 5);unionfind.UnionSet(2, 6);unionfind.UnionSet(7, 8);unionfind.UnionSet(7, 9);std::cout << "有多少组：" << unionfind.CountSet() << std::endl;//查找陈悦在哪一组std::cout << "陈悦的组长：" << unionfind.Find("陈悦") << std::endl;//查找是否在一组std::cout << "陈悦和张宇：" << unionfind.IsSame("陈悦", "张宇") << std::endl;std::cout << "陈悦和刘阳：" << unionfind.IsSame("陈悦", "刘阳") << std::endl;//合并unionfind.UnionSet(0, 2);std::cout << "有多少组：" << unionfind.CountSet() << std::endl;//查找陈悦在哪一组std::cout << "陈悦的组长：" << unionfind.Find("陈悦") << std::endl;//查找是否在一组std::cout << "陈悦和张宇：" << unionfind.IsSame("陈悦", "张宇") << std::endl;std::cout << "陈悦和刘阳：" << unionfind.IsSame("陈悦", "刘阳") << std::endl;return 0;
}