廊坊优化网站排名,如何制作课程网站模板下载地址,51网页游戏官网,网站建设公司专业网站开发研发目录#xff1a; 并查集的概念代码实现 LeetCode例题 并查集的概念
将n个不同的元素划分成一些不相交的集合。开始时#xff0c;每个元素自成一个单元元素集合#xff0c;然后按一定的规律将归于同一组元素的集合合并。在此过程中反复遇到查询某一个元素属于那个集合的运算… 目录 并查集的概念代码实现 LeetCode例题 并查集的概念
将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中反复遇到查询某一个元素属于那个集合的运算这种抽象的数据类型称为并查集。 主要思想用集合中的一个元素代表集合。
代码实现
#includeiostream
#includevector
class UnionFindSet
{
public:UnionFindSet(size_t n)//构造函数:_ufs(n,-1){}void Union(int x1,int x2)//合并根{int root1 FindRoot(x1);int root2 FindRoot(x2);if (root1 root2)//如果本身在一个集合就没必要合并了 return;_ufs[root1] _ufs[root2];//2个下标相加_ufs[root2] root1;//存一下根的下标}int FindRoot(int x)//查找根{ int parent x;while (_ufs[parent] 0)//说明不是根{parent _ufs[parent];}return parent;//f返回的编号是负数就是根}bool InSet(int x1, int x2){return FindRoot(x1) FindRoot(x2);//相等说明同一个根在同一个集合}size_t SetSize()//有几个集合{size_t size 0;for (size_t i 0; i _ufs.size(); i){if (_ufs[i] 0)//判断有几个负数就有几个集合,因为负数是根{size;}}return size;}private:vectorint _ufs;//编号找人
};LeetCode例题
例题一 116. 省份数量 有 n 个城市其中一些彼此相连另一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected 其中 isConnected[i][j] 1 表示第 i 个城市和第 j 个城市直接相连而 isConnected[i][j] 0 表示二者不直接相连。返回矩阵中省份的数量。 示例 1 输入isConnected [[1,1,0],[1,1,0],[0,0,1]] 输出2
示例 2 输入isConnected [[1,0,0],[0,1,0],[0,0,1]] 输出3
提示 1 n 200 n isConnected.length n isConnected[i].length isConnected[i][j] 为 1 或 0 isConnected[i][i] 1 isConnected[i][j] isConnected[j][i] 代码解答
class Solution {
public:int findCircleNum(vectorvectorint isConnected) {vectorint ufs(isConnected.size(),-1);//手动函数auto findRoot[ufs](int x){while(ufs[x]0)//是负数才是根xufs[x];return x; };for(size_t i0;iisConnected.size();i){for(size_t j0;jisConnected[i].size();j){if(isConnected[i][j]1){//合并集合int root1findRoot(i);int root2findRoot(j);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;//root2变成root1的孩子,root2的下标存的是root1是0}}}}int n0;for(auto e: ufs){if(e0)n;}return n;}
};例题二 990. 等式方程的可满足性 给定一个由表示变量之间关系的字符串方程组成的数组每个字符串方程 equations[i] 的长度为 4并采用两种不同的形式之一“a等于b” 或 “a!b”。在这里a 和 b 是小写字母不一定不同表示单字母变量名。只有当可以将整数分配给变量名以便满足所有给定的方程时才返回 true否则返回 false。 代码解答
class Solution {
public:bool equationsPossible(vectorstring equations) {vectorint ufs (26,-1);//26个字母的映射关系auto findRoot[ufs](int x){while(ufs[x]0)xufs[x];return x;};for(auto str: equations){if(str[1]){int root1findRoot(str[0]-a);int root2findRoot(str[3]-a);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;//root2变成root1的孩子} }}
//判断不相等的在不在一个集合在就相悖并返回falsefor(auto str: equations){if(str[1]!){int root1findRoot(str[0]-a);int root2findRoot(str[3]-a);if(root1root2){return false;} }}return true;}
};
