江苏省建设执业资格注册中心网站新的龙岗网站建设

江苏省建设执业资格注册中心网站,新的龙岗网站建设,网站的默认首页,th7 wordpress主题一、并查集的原理 在一些应用问题中#xff0c;需要将n个不同的元素划分成一些不相交的集合#xff0c;开始时#xff0c;每个元素自成一个单元素集合#xff0c;然后按一定规律将同一组的元素集合合并。在此过程中要反复用到查询某个元素归属于哪个集合的运算#xff0c;…一、并查集的原理在一些应用问题中需要将n个不同的元素划分成一些不相交的集合开始时每个元素自成一个单元素集合然后按一定规律将同一组的元素集合合并。在此过程中要反复用到查询某个元素归属于哪个集合的运算适合于描述这类问题的抽象数据结构类型称为并查集union-find-set比如作者有大学同学高中同学初中同学他们彼此不认识。就会分为三个集合。按10人来算将其按编号分为0-9,分为不同的团体用数组来表示该树形关系数组中的非负数代表其父节点负数表示该结点为根结点且该树形有abs负数个结点。之后机缘巧合下大学同学和初中同学在一场聚会中认识了就将其合并为一个集合。通过以上例子可知并查集一般可解决以下问题1.查找元素属于哪一个集合2.查看两个元素是否属于同一个集合3.将两个集合归并为一个集合4.得到集合的个数二、并查集的实现1.这里我使用map存储名字和其对应vector的下标vector来存储其关系。class UnionFindSet{ public: UnionFindSet(int n) { v.reserve(n); } private: vectorint v; mapT,int m; };2.push实现去添加新元素void push(T name) { v.push_back(-1); m[name] v.size() - 1; } void push(const T name) { v.push_back(-1); m[name] v.size()-1; }这里实现右值引用和const左值引用两个版本3.给一个元素找见其元素所在集合的位置//给一个元素找见其元素所在集合的位置 int UnionFind(const T name) { if (m.count(name) 0) { return -1; } else { //通过循环遍历找见v[index]为负数的位置 //该index就为根节点的位置 int index m.find(name)-second; while (v[index] 0) { index v[index]; } return index; } }4.查找集合的个数//集合的个数 size_t Count()const { size_t count 0; for (int i 0; i v.size(); i) { if (v[i] 0) { count; } } return count; }5.查找两个元素是否为同一个集合并合并//合并两个元素为同一个集合 bool merge(const T name1, const T name2) { //查找两个元素是不是同一个集合 int x1 UnionFind(name1); int x2 UnionFind(name2); if (x1 x2) {//因为有相同的根节点所以为同一个集合 return false; } else { v[x1] v[x2];//将v[x2]存储的内容加在v[v1]上更新新集合的结点数量 v[x2] x1;//将v[x2]指向父节点 return true; } } //也可合并多个元素利用可变参数包 templateclass...Args void merge(const T name1, const T name2, Args... args) { merge(name1, name2); if constexpr (sizeof...(args) 0) {//constexpr可以在编译时检查防止传参出现问题 merge(name2, forwardArgs(args)...);//这里用完美转发去保持其右值属性不变。 } }三、并差集的应用1.省份数量https://leetcode.cn/problems/number-of-provinces/description/class Solution { public: int findCircleNum(vectorvectorint isConnected) { vectorint v; v.resize(isConnected.size(),-1); auto find[v](int index){//寻找根节点的数组下标 while(v[index]0){ indexv[index]; } return index; }; auto merge[v,find](int a,int b){//合并两个集合 int a1find(a); int b1find(b); if(a1!b1){ v[a1]v[b1]; v[b1]a1; } }; for(int i0;iisConnected.size();i){ for(int j0;jisConnected.size();j){ if(isConnected[i][j]1){//建立集合的关系 merge(i,j); } } } int count0; for(int i0;iv.size();i){ if(v[i]0){//判断“省份”的数量 count; } } return count; } };2.等式方程的可满足性https://leetcode.cn/problems/satisfiability-of-equality-equations/description/class Solution { public: bool equationsPossible(vectorstring equations) { vectorint v; v.resize(26,-1); auto find[v](int index){ while(v[index]0){ indexv[index]; } return index; }; auto merge[v,find](int x,int y){ int x1find(x); int y1find(y); if(x1!y1){ v[x1]v[y1]; v[y1]x1; } }; for(auto e:equations){ if(e[1]){//先将等于关系建立起来 merge(e[0]-a,e[3]-a); } } for(auto e:equations){ if(e[1]!){//判断两个不等的元素是否有相等关系 int xfind(e[0]-a); int yfind(e[3]-a); if(xy){//有就返回失败 return false; } } } return true;//遍历结束返回成功 } };