网站上传安装,网站英文域名,网站产品分类设计,大连商城网站制作1. 什么是并查集#xff1f; 在计算机科学中#xff0c;并查集#xff08;英文#xff1a;Disjoint-set data structure#xff0c;直译为不数据结构交集#xff09;是一种数据结构#xff0c;用于处理一些不交集#xff08;Disjoint sets#xff0c;一系列没有重复元…1. 什么是并查集 在计算机科学中并查集英文Disjoint-set data structure直译为不数据结构交集是一种数据结构用于处理一些不交集Disjoint sets一系列没有重复元素的集合的合并及查询问题。 举个简单的例子
一个组织里来个10个新人它们的编号为从1~10假设此时它们根据彼此的老家而互相亲近即形成一个小团体我们要将这10个人划分成不同的小团体这样划分后形成的结果就是并查集。
接下来我们就来模拟这10个人的划分过程首先我们可以将每个人的初始值设置为-1当两个人都属于同一个小团体时将其中一个人的-1加到另一个人身上自己的值指向另一个人的下标 此时另一个人就作为这一个小团体的根这之后如果有新的人进入这个团体将新人的-1加到根上再让新人指向根的下标。这样操作后所有人中只要自己的值0则表明自己是一个团队的根绝对值表示团队人数而团体中的其他人均指向这个根。
2. 并查集的常见操作
我们通过上面的模拟我们可以发现并查集的主要操作主要是合并查找根查看团队个数
我们使用C实现这个数据结构有
#pragma once
#include vectorusing namespace std;class UnionFindSet
{
public:// 将并查集中的所有元素初始化为-1UnionFindSet(size_t n):_ufs(n, -1){}// 查找根int FindRoot(int x);// 合并void Union(int x1, int x2);// 查看集合个数size_t UnionCount(int x);private:vectorint _ufs;
};
1. 查找根
// 查找根
int FindRoot(int x)
{if (x _ufs.size()){throw invalid_argument(无效参数!);return -1;}int root x;while (_ufs[root] 0) // 不为根就向上查找{root _ufs[root];}return root;
}
2. 合并
在合并时有可能会出现两个团队互相合并的情况此时我们只需要将其中一个团队的根的值加到另一个团队的根上再让自己指向另一个团队的根即可即
// 合并
void Union(int x1, int x2)
{int root1 FindRoot(x1);int root2 FindRoot(x2);// 两个人属于不同的集合时才需要进行合并if (root1 ! root2){_ufs[root1] _ufs[root2];_ufs[root2] root1;}
}
3. 查看集合个数
// 查看集合个数
size_t UnionCount()
{size_t ret 0;for (auto e : _ufs){if (e 0) ret;}return ret;
}
3. 并查集的实际应用
1. 省份数量
题目链接LCR 116. 省份数量 - 力扣LeetCode 解析分析题目如果这道题使用并查集就没有那么难整体思路就是如果两个城市相连就将他们合并为一个省份最终返回省份个数即可
解法一使用并查集数据结构 即
class UnionFindSet
{
public:// 将并查集中的所有元素初始化为-1UnionFindSet(size_t n):_ufs(n, -1){}// 查找根int FindRoot(int x){if (x _ufs.size()){throw invalid_argument(无效参数!);return -1;}int root x;while (_ufs[root] 0) // 不为根就向上查找{root _ufs[root];}return root;}// 合并void Union(int x1, int x2){int root1 FindRoot(x1);int root2 FindRoot(x2);// 两个人属于不同的集合时才需要进行合并if (root1 ! root2){_ufs[root1] _ufs[root2];_ufs[root2] root1;}}// 查看集合个数size_t UnionCount(){size_t ret 0;for (auto e : _ufs){if (e 0) ret;}return ret;}private:vectorint _ufs;
};class Solution
{
public:int findCircleNum(vectorvectorint 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] 1){ufs.Union(i, j);}return ufs.UnionCount();}
}; 解法二直接运用并查集思想
即
2. 等式方程的可满足性
题目链接990. 等式方程的可满足性 - 力扣LeetCode
