第7讲：并查集

目录本节目标1. 并查集原理2. 并查集实现3. 并查集应用省份数量等式方程的可满足性本节目标并查集原理并查集实现并查集应用1. 并查集原理在一些应用问题中需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于哪个集合的运算。适合于描述这类问题的抽象数据类型称为并查集union-find set。比如某公司今年校招全国总共招生 10 人西安招 4 人成都招 3 人武汉招 3 人10 个人来自不同的学校起先互不相识每个学生都是一个独立的小团体现给这些学生进行编号{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}给以下数组用来存储该小集体数组中的数字代表该小集体中具有成员的个数。负号下文解释毕业后学生们要去公司上班每个地方的学生自发组织成小分队一起上路于是西安学生小分队s1{0,6,7,8}成都学生小分队s2{1,4,9}武汉学生小分队s3{2,3,5}就相互认识了10 个人形成了三个小团体。假设由三个群主 0、1、2 担任队长负责大家的出行。一趟火车之旅后每个小分队成员就互相熟悉成为了一个朋友圈。从上图可以看出编号 6、7、8 同学属于 0 号小分队该小分队中有 4 人包含队长 0编号为 4 和 9 的同学属于 1 号小分队该小分队有 3 人包含队长 1编号为 3 和 5 的同学属于 2 号小分队该小分队有 3 个人包含队长 2。仔细观察数组中的内容变化可以得出以下结论数组的下标对应集合中元素的编号数组中如果为负数负号代表根数字代表该集合中元素个数数组中如果为非负数代表该元素双亲在数组中的下标在公司工作一段时间后西安小分队中 8 号同学与成都小分队 1 号同学奇迹般地走到了一起两个小圈子的学生相互介绍最后成为了一个小圈子现在 0 集合有 7 个人2 集合有 3 个人总共两个朋友圈。通过以上例子可知并查集一般可以解决以下问题查找元素属于哪个集合沿着数组表示的树形关系一直找到根即树中元素为负数的位置。查看两个元素是否属于同一个集合沿着数组表示的树形关系往上一直找到树的根如果根相同表明在同一个集合否则不在。将两个集合归并成一个集合将两个集合中的元素合并。将一个集合名称改成另一个集合的名称。集合的个数遍历数组数组中元素为负数的个数即为集合的个数。2. 并查集实现classUnionFindSet{public:// 初始时将数组中元素全部设置为-1UnionFindSet(size_t size):_ufs(size,-1){}// 给一个元素的编号找到该元素所在集合的名称intFindRoot(intindex){// 如果数组中存储的是负数找到否则一直继续while(_ufs[index]0){index_ufs[index];}returnindex;}boolUnion(intx1,intx2){introot1FindRoot(x1);introot2FindRoot(x2);// x1已经与x2在同一个集合if(root1root2)returnfalse;// 将两个集合中元素合并_ufs[root1]_ufs[root2];// 将其中一个集合名称改变成另外一个_ufs[root2]root1;returntrue;}// 数组中负数的个数即为集合的个数size_tCount()const{size_t count0;for(autoe:_ufs){if(e0)count;}returncount;}private:vectorint_ufs;};3. 并查集应用LCR 116. 省份数量classSolution{public:intfindCircleNum(vectorvectorintisConnected){// 手动控制并查集vectorintufs(isConnected.size(),-1);// 查找根autofindRoot[ufs](intx){while(ufs[x]0)xufs[x];returnx;};for(size_t i0;iisConnected.size();i){for(size_t j0;jisConnected[i].size();j){if(isConnected[i][j]1){// 合并集合introot1findRoot(i);introot2findRoot(j);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;}}}}intn0;for(autoe:ufs){if(e0)n;}returnn;}};990. 等式方程的可满足性/* 解题思路 1. 将所有两端的字符合并到一个集合中 2. 检测!两端的字符是否在同一个集合中如果在则不满足如果不在则满足 */classSolution{public:boolequationsPossible(vectorstringequations){vectorintufs(26,-1);autofindRoot[ufs](intx){while(ufs[x]0)xufs[x];returnx;};// 第一遍先把相等的值加到一个集合中for(autostr:equations){if(str[1]){introot1findRoot(str[0]-a);introot2findRoot(str[3]-a);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;}}}// 第二遍先检查不相等的字符是否在一个集合中在一起就相悖了// 返回falsefor(autostr:equations){if(str[1]!){introot1findRoot(str[0]-a);introot2findRoot(str[3]-a);if(root1root2){returnfalse;}}}returntrue;}};