【数据结构与算法-高阶】并查集
🥕个人主页:开敲🍉
🔥所属专栏:数据结构与算法🍅
🌼文章目录🌼
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}。假设 0、1、2分别是三个小分队的队长。
在一趟漫长的火车旅行之后,小分队里的人都熟络了起来,成为了一个朋友圈:
此时这个朋友圈在数组中的形式就变成了这样(还是先别管数组中存储的值的意义,后面会解释):
从上图就可以清晰明白:编号 6、7、8的同学属于 0号 的小队;编号4、9的同学属于 1号 的小队;编号3、5的同学属于 2号 的小队。
此时我们仔细观察一下数组中的值加以思考就能得出以下结论:
① 数组的下标就是同学的编号
② 数组中为负数的值所对应的下标就是队长的编号,我们在这里称之为 根
③ 数组中所有为非负数的值也是队长的编号,也就是非负数的值指向根
在公司工作了一段时间后,西安小分队中的8号同学与成都小分队的1号同学关系变得越来越亲密,经过这两位同学的相互介绍,西安小分队和成都小分队最终融合成了一个圈子:
此时数组也变换成:
现在0号的队伍中有了7个人,2号的队伍中有2个人,总共两个朋友圈,也可以说,总共两个根。
通过上述例子我们可以知道,并查集一般可以解决以下问题:
① 查找元素属于哪个集合:沿着该元素位置所存储的值一路跳转查找,直到遇到存储的值为负数的下标,就是集合的 根
② 查看两个元素是否属于同一个集合:依旧是跳转查找到存储的值为负数的下标,判断两个元素是否指向同一个根
③ 将两个集合归并为一个集合
④ 判断集合的个数
2. 并查集实现
//并查集
template <class T>
class Union
{
public:Union(size_t n):_a(n,-1){}//并集void UnionCom(size_t x,size_t y){//寻找x、y所在集合的根,用root1、root2接收int root1 = FindRoot(x);int root2 = FindRoot(y);if (root1 == root2) return;//如果两个元素在同一个集合,则无需合并,直接返回_a[root1] += _a[root2];//将 root2 存储的值存入 root1 中_a[root2] = root1;//将 root2 归并到 root1下}//寻根int FindRoot(size_t x){int flag = x;while (_a[flag] >= 0) flag = _a[flag];//沿着存储的值一路查找,直到找到存储的值为负数的下标return flag;}//求集合个数size_t UnionCount(){size_t count = 0;for (int i = 0; i < _a.size(); i++){if (_a[i] < 0) count++;//存储的值是负数的就是集合的根}return count;}//判断是否在同一集合中bool UnionSam(size_t x, size_t y){return (_a[x] == _a[y] && _a[x] != -1);}private:vector<int> _a;
};
3. 并查集应用
下面题目的题解在:【每日刷题】Day134-CSDN博客 中。
LCR 116. 省份数量 - 力扣(LeetCode)
class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int ans = 0;vector<int> ufs(isConnected.size(),-1);auto findRoot = [&ufs](int x){while(ufs[x]>=0) x = ufs[x];return x;};for(int i = 0;i<isConnected.size();i++){for(int j = 0;j<isConnected[i].size();j++){if(isConnected[i][j]){int root1 = findRoot(i);int root2 = findRoot(j);if(root1!=root2){ufs[root1]+=ufs[root2];ufs[root2] = root1;}}}}for(int i = 0;i<ufs.size();i++){if(ufs[i]<0) ans++;}return ans;}
};
990. 等式方程的可满足性 - 力扣(LeetCode)
class Solution {
public:bool equationsPossible(vector<string>& equations) {vector<int> ufs(26,-1);auto findRoot = [&ufs](int x){while(ufs[x]>=0) x = ufs[x];return x;};//相等放入同一集合for(auto str:equations){if(str[1]=='='){int root1 = findRoot(str[0]-'a');int root2 = findRoot(str[3]-'a');if(root1!=root2){ufs[root1]+=ufs[root2];ufs[root2] = root1;}}}//不相等判断是否在同一个集合,如果在则相悖for(auto str:equations){if(str[1]=='!'){int root1 = findRoot(str[0]-'a');int root2 = findRoot(str[3]-'a');if(root1==root2) return false;}}return true;}
};