并查集-547.省份的数量-力扣(LeetCode)
并查集-547.省份的数量-力扣(LeetCode)
专栏：力扣刷题录_1白天的黑夜1的博客-CSDN博客、企鹅程序员：Linux 系统与网络编程_1白天的黑夜1的博客-CSDN博客
目录
一、题目解析
1、省份是一组直接或间接相连的城市(没有链接的单独城市也是省份)
2、isConnected[i][j]== 1 or 0，并且isConnected[i][j] == isConnected[j][i]
二、算法原理
解法1：自己造轮子(写一个并查集出来)
具体步骤：
1、将自己写好的并查集直接复制粘贴过来
2、通过size()获取城市的数目初始化并查集父指针数组，通过并查集构造函数
3、遍历二维数组isConnected
3.1、如果isConnected[i][j] == 1，通过Uoion()合并函数，合并i和j；如果遇到isConnected[j][i] == 1，在Union()函数内会判断i和j的根是否相同，相等则不会合并。
3.2、如果isConnected[i][j] ==0，循环继续
4、循环结束后，通过SetSize()返回并查集中的集合个数，也就是省份的个数
解法2：通过lambda函数实现核心合并功能
具体步骤：
1、创建一个vector数组用于充当父指针数组，通过vector构造函数全部初始化为-1
2、将找根函数，用lambda表达式实现一个简单的匿名函数
3、遍历isConnected二维数组
3.1、如果isConnected[i][j] == 1，则说明可以开始合并了，但还需判断根是否相同
3.2、通过lambda表达式实现的找根匿名函数找到i和j的根，如果不相等，则合并，将其中合并根父指针数组存的值+=被合并根的父指针数组存的值，并将被合并根的父指针数组的值修改为合并的根(这里就是合并的主逻辑)
3.3、如果isConnected[i][j] == 0，则循环继续
4、在并查集中，如果是根，其值为负数，所以遍历一遍创建的vecter的数组，统计省份的数量
依据算法原理或者你自己想的解法，各位读者可以去尝试一番，提升自己的代码能力
三、代码示例
解法1：
解法2：
看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！
一、题目解析
1、省份是一组直接或间接相连的城市(没有链接的单独城市也是省份)
2、isConnected[i][j]== 1 or 0，并且isConnected[i][j] == isConnected[j][i]
二、算法原理
若读者对并查集比较陌生，或者有点遗忘了，可以移步博主的博客去学习或回顾一下
解法1：自己造轮子(写一个并查集出来)
我们可以发现，将两个城市连接起来，是不是有点类似我们并查集的合并，而最终返回的省份个数就相当于我们查询并查集中有多少个集合。
具体步骤：
1、将自己写好的并查集直接复制粘贴过来
2、通过size()获取城市的数目初始化并查集父指针数组，通过并查集构造函数
3、遍历二维数组isConnected
3.1、如果isConnected[i][j] == 1，通过Uoion()合并函数，合并i和j；如果遇到isConnected[j][i] == 1，在Union()函数内会判断i和j的根是否相同，相等则不会合并。
3.2、如果isConnected[i][j] ==0，循环继续
4、循环结束后，通过SetSize()返回并查集中的集合个数，也就是省份的个数
解法2：通过lambda函数实现核心合并功能
如果我们以后遇到了类似的题也能直接粘贴我们自己造的轮子(并查集)吗？这肯定是不现实的，在经过并查集的学习后，我们掌握了其基本理念，结合我们所学的lambda表达式，我们也能解决该题。
具体步骤：
1、创建一个vector数组用于充当父指针数组，通过vector构造函数全部初始化为-1
2、将找根函数，用lambda表达式实现一个简单的匿名函数
Lambda表达式是C++11引入的一种简便方法，用于在被调用的位置或作为参数传递给函数的位置定义匿名函数对象（闭包）。它的基本语法如下：
[capture list] (parameter list) -> return type { function body }
其中：
- capture list 是捕获列表，用于指定Lambda表达式可以访问的外部变量，以及是按值还是按引用的方式访问。
- parameter list 是参数列表，用于表示Lambda表达式的参数，可以为空，也可以指定参数的类型和名称。
- return type 是返回值类型，可以省略，由编译器根据函数体推导。
- function body 是函数体，用于表示Lambda表达式的具体逻辑。
捕获方式
Lambda表达式支持多种捕获方式：
- 值捕获：在捕获列表中使用变量名，表示将该变量的值拷贝到Lambda表达式中。
- 引用捕获：在捕获列表中使用&加变量名，表示将该变量的引用传递到Lambda表达式中。
- 隐式捕获：在捕获列表中使用=或&，表示按值或按引用捕获Lambda表达式中使用的所有外部变量。
- 初始化捕获：C++14引入的一种新的捕获方式，允许在捕获列表中使用初始化表达式。
3、遍历isConnected二维数组
3.1、如果isConnected[i][j] == 1，则说明可以开始合并了，但还需判断根是否相同
3.2、通过lambda表达式实现的找根匿名函数找到i和j的根，如果不相等，则合并，将其中合并根父指针数组存的值+=被合并根的父指针数组存的值，并将被合并根的父指针数组的值修改为合并的根(这里就是合并的主逻辑)
3.3、如果isConnected[i][j] == 0，则循环继续
4、在并查集中，如果是根，其值为负数，所以遍历一遍创建的vecter的数组，统计省份的数量
依据算法原理或者你自己想的解法，各位读者可以去尝试一番，提升自己的代码能力
三、代码示例
解法1：
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;
//小的做根
if (root1 > root2) swap(root1, root2);
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}
int FindRoot(int x)//找根
{
int parent = x;
while (_ufs[parent] >= 0)
{
parent = _ufs[parent];
}
return parent;
}
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:
vector<int> _ufs;
};
//解法1：通过并查集
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected)
{
UnionFindSet ufs(isConnected.size());
for(int i = 0;i<isConnected.size();i++)
{
for(int j = 0;j<isConnected[i].size();j++)
{
if(isConnected[i][j])
{
ufs.Union(i,j);
}
}
}
return ufs.SetSize();
}
};
解法2：
//解法2：写一个findroot的lambda表达式
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected)
{
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;
}
}
}
}
int n = 0;
for(auto e : ufs)
if(e<0) ++n;
return n;
}
};
看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！
腾讯云开发者
