一、并查集的概念在一些场景中需要将n个不同元素划分为一些不相交的集合。开始时每个元素各成一个元素然后按一定的规律将属于同一组的元素合并。这个过程中需要反复用到查询一个元素是否属于某个集合的算法。适合用于这种场景的数据结构是并查集Union-Find Set并查集的底层结构本质上是一片森林多棵树的集合比如我现在有九个数据元素给他们编号0~8按照某种需求这些数据被分组合并为按照其他需求这些树可以继续合并下去…而这个森林可以用一个数组记录下来元素的关系我们可以规定并查集用数组下标代表每个元素数组内容代表元素之间的关系数组下标代表元素编号如果数组内容为负整数代表这个下标是根绝对值表示它这棵树的元素个数如果数组内容为非负整数代表这个下标不是根数组内容是它的父亲在数组中的下标比如上面的森林例子用并查集数组表示就是如果元素的数据类型不能直接作为数组下标只要在实现中用std::map之类的结构建立元素到下标的映射关系就能解决了通过并查集的特点可以看出并查集一般能解决查找元素属于哪个集合沿着数组一直找到元素为负数就是根查看两个元素是否属于一个集合看看这两个元素的根是否相同将两个集合归并为一个集合假如要将下标a的树合并到下标b的树中arr[b] arr[a]arr[a] b即可即令1成为0的一个孩子统计集合的个数统计数组中元素为负数的个数二、并查集的实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#pragma once#includevector#includeiostreamusingnamespacestd;classUnionFindSet{public:UnionFindSet(intsize):_set(size, -1)// 初始时每个数据各是一棵树元素均为-1{ }// 查找一个数据属于哪个集合找根元素的下标intFindRoot(inti){while(_set[i] 0){i _set[i];}returni;}// 合并两个数据所在的集合voidUnion(inti1,inti2){// 找这两个数据的根下标introot1 FindRoot(i1);introot2 FindRoot(i2);if(root1 ! root2){_set[root1] _set[root2];_set[root2] root1;}// 如果root1 root2说明这两个数据本就在一个集合不用合并}// 判断两个数据是否在同一个集合boolIsSameSet(inti1,inti2){returnFindRoot(i1) FindRoot(i2);}// 统计集合个数intSetCount(){intret 0;for(intn : _set){if(n 0)ret;}returnret;}private:vectorint _set;};测试三、算法题中的应用并查集的特点在某些算法题中很有用省份数量1234567891011121314151617181920212223242526272829303132333435363738394041424344454647classSolution {public:// 并查集, 统计集合数量intfindCircleNum(vectorvectorint isConnected) {vectorint ufs(isConnected.size(), -1);auto findRoot [ufs](inti){while(ufs[i] 0){i ufs[i];}returni;};auto Union [ufs, findRoot](inti1,inti2){introot1 findRoot(i1);introot2 findRoot(i2);if(root1 ! root2){ufs[root1] ufs[root2];ufs[root2] root1;}};auto SetCount [ufs](){intret 0;for(intn : ufs){if(n 0)ret;}returnret;};for(inti 0; i isConnected.size(); i){for(intj 0; j isConnected[i].size(); j){if(isConnected[i][j] 1){Union(i, j);}}}returnSetCount();}};等式方程的可满足性12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849classSolution {public:// 并查集数组大小26// 遍历一次把所有的两个字母放到一个集合再遍历一次看!的两个字符是否都在集合中出现过出现过则falseboolequationsPossible(vectorstring equations) {vectorint ufs(26, -1);auto findRoot [ufs](inti){while(ufs[i] 0){i ufs[i];}returni;};auto Union [ufs, findRoot](inti1,inti2){introot1 findRoot(i1);introot2 findRoot(i2);if(root1 ! root2){ufs[root1] ufs[root2];ufs[root2] root1;}};for(string s : equations){if(s[1] ){Union(s[0]-a, s[3]-a);}}for(string s : equations){if(s[1] !){introot1 findRoot(s[0]-a);introot2 findRoot(s[3]-a);if(root1 root2){returnfalse;}}}returntrue;}};总结到此这篇关于C并查集的原理与使用方法的文章就介绍到这了