建站工具介绍,广东省建设工程执业中心网站,小程序小游戏开发,网站建设 公司 常州并查集 1.并查集原理2.并查集实现3.并查集应用4.并查集的路径压缩 1.并查集原理
在一些应用问题中#xff0c;需要将n个不同的元素划分成一些不相交的集合。开始时#xff0c;每个元素自成一个单元素集合#xff0c;然后按一定的规律将归于同一组元素的集合合并。在此过程中… 并查集 1.并查集原理2.并查集实现3.并查集应用4.并查集的路径压缩 1.并查集原理
在一些应用问题中需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-findset)。
如何合并两个集合
先找到两个集合的根部负数为根部。以合并AB为例子假设让B合并到AA减去B的值即变成-2然后让B的值变成A的下标0。
观察合并过程可以得出以下结论
数组的下标对应集合中元素的编号数组中如果为负数负号代表根数字代表该集合中元素个数数组中如果为非负数代表该元素双亲在数组中的下标 2.并查集实现
并查集一般可以解决以下问题
查找元素属于哪个集合 沿着数组表示树形关系以上一直找到根(即树中中元素为负数的位置)
int FindRoot(int x) //找根的下标位置
{int par x;while (_ufs[par] 0) //如果当前大于0说明未到根部更新到父亲下标{par _ufs[par];}return par;
}查看两个元素是否属于同一个集合 沿着数组表示的树形关系往上一直找到树的根如果根相同表明在同一个集合否则不在
bool InSet(int x1, int x2)
{if (FindRoot(x1) FindRoot(x2)){return true;}return false;
}将两个集合归并成一个集合 前面讲过不赘述。
void Union(int x1, int x2) //联合这两棵树默认x2并到x1
{int root1 FindRoot(x1);int root2 FindRoot(x2);if (abs(_ufs[root1]) abs(_ufs[root2])) //让小的一方并到大的一方就这样swap(root1, root2);if (root1 ! root2) //本来不是同一个树集合{_ufs[root1] _ufs[root2];_ufs[root2] root1;}
}集合的个数 遍历数组数组中元素为负数的个数即为集合的个数。
int SetSize()const //返回树的个数
{int size 0;for (auto e : _ufs)if (e 0) size;return size;
}完整实现
class UnionFindSet {
public:UnionFindSet(size_t size) //一开始全都设置为-1:_ufs(size, -1){}void Union(int x1, int x2) //联合这两棵树默认x2并到x1{int root1 FindRoot(x1);int root2 FindRoot(x2);if (abs(_ufs[root1]) abs(_ufs[root2])) //让小的一方并到大的一方就这样swap(root1, root2);if (root1 ! root2) //本来不是同一个树集合{_ufs[root1] _ufs[root2];_ufs[root2] root1;}}int FindRoot(int x) //找根的下标位置{int par x;while (_ufs[par] 0){par _ufs[par];}return par;}bool InSet(int x1, int x2){if (FindRoot(x1) FindRoot(x2)){return true;}return false;}int SetSize()const //返回树的个数{int size 0;for (auto e : _ufs)if (e 0) size;return size;}
private:vectorint _ufs;
};3.并查集应用
省份数量 //讲解并查集一个城市就是一个集合
//1初始每个城市自成一省
//2如果isConnected[i][j]为1说明i城市和j城市在一个省合并
//3合并完成后遍历数组负数有几个集合省份就有几个
//实际并不一定要实现完整的功能一般需要的功能是找根部函数class Solution {
public:int findCircleNum(vectorvectorint isConnected) {vectorint 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] 1) //有关系{int root1 FindRoot(i), root2 FindRoot(j);if(root1 ! root2) //不是同个集合{ufs[root1] ufs[root2]; //这一步本题没必要其实ufs[root2] root1;}}int ret 0;for(auto e : ufs) if(e 0) ret;return ret;}
};等式方程的可满足性 //思路并查集先遍历一次建立起集合联系如果a!b但a与b在一个集合中就是相悖的返回false
// 本题只有小写字母可用0对应a,1对应b依次类推
class Solution {
public:bool equationsPossible(const vectorstring equations) {vectorint 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), root2 FindRoot(str[3] - a);if (root1 ! root2){ufs[root1] ufs[root2]; //这一步没必要ufs[root2] root1;}}//再遍历一次如果在一个集合中就返回false;for (auto str : equations)if (str[1] !){int root1 FindRoot(str[0] - a), root2 FindRoot(str[3] - a);if (root1 root2){return false;}}return true;}
};4.并查集的路径压缩
并查集一般无需压缩路径但对数据量大的情况想加快效率就需要压缩路径。
原理
可在查询时压缩比如6-5-4-3根部先找到根部3。把6记录下来一路向上直到根即让6、5、4直接做3的孩子从而完成压缩。
int FindRoot(int x) //找根的下标位置
{int root x;while (_ufs[root] 0){root _ufs[root];}//压缩路径while (_ufs[x] 0){int par _ufs[x]; //先记录父亲下标_ufs[x] root;x par;}return root;
}
