怎么自己注册网站,义乌做公司网站,兰州企业网站建设哪家好,单人给一个公司做网站费用目录
1. 并查集原理
问题背景
名称与编号映射
数据结构设计
2. 并查集基本操作
(1) 初始化
(2) 查询根节点 (FindRoot)
(3) 合并集合 (Union)
(4) 集合操作总结
并查集优化
(1) 路径压缩
(2) 按秩合并
3. 并查集的应用
(1) 统计省份数量
(2) 判断等式方程是否成…目录
1. 并查集原理
问题背景
名称与编号映射
数据结构设计
2. 并查集基本操作
(1) 初始化
(2) 查询根节点 (FindRoot)
(3) 合并集合 (Union)
(4) 集合操作总结
并查集优化
(1) 路径压缩
(2) 按秩合并
3. 并查集的应用
(1) 统计省份数量
(2) 判断等式方程是否成立 并查集是一种用于处理 元素分组和集合操作 的数据结构主要功能是支持以下两种操作
合并将两个集合合并成一个集合。查询判断某个元素属于哪个集合。
并查集实际上是由多棵 互不相交的树 组成的森林以下是详细的整理内容。 1. 并查集原理
问题背景
在一些问题中需要将 n 个不同的元素划分为若干个互不相交的集合并支持以下操作
查询某个元素所属的集合。合并两个集合。
例如某公司校招的 10 名学生分别来自不同地区起初各自独立。根据他们的交流情况可以将其分为几个小团体。通过并查集可以很好地表示这些分组关系并实现高效的集合操作。
首先先给这些学生进行编号{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体数组中的数字代表该小集体中具有成员的个数。(负号下文解释) 继续往下看如何描述他们之间的关系呢 西安学生小分队s1{0,6,7,8}成都学生小分队s2{1,4,9}武汉学生小分队s3{2,3,5}就相互认识了10个人形成了三个小团体。假设右三个群主0,1,2担任队长负责大家的出行。如何表示这三个集合呢
很简单把他们建立三颗树形结构。一个数据结构有多颗树不就是之前所说的森林了。如何建树呢一个集体随便选取一个节点作根剩下节点取做它的孩子。 那我们如何来表示这里的集合结构呢
并查集是森林森林是由多个树组成这里用两层来表示这里的关系。
像堆类似用数组下标表示关系双亲表示法存储双亲的下标 仔细观察数组中内融化可以得出以下结论
数组的下标对应集合中元素的编号数组中如果为负数负号代表根数字绝对值 代表该集合中元素个数数组中如果为非负数代表该元素双亲在数组中的下标 合并过程 继续往下看如何将已经有的集合合并呢 刚才都是独立的集合直接合并现在是已经有集合怎么合并呢?
比如说在公司工作一段时间后西安小分队中8号同学与成都小分队4号同学奇迹般的走到了一起两个小圈子的学生相互介绍最后成为了一个小圈子怎么合并呢
不能直接合并而是找到两个数的根让根合并。 找根很简单看自己位置保存的是不是负数如果是负数自己就是根了如果不是负数保存的就是双亲的下标了就去看看双亲下标保存的是不是负数不是负数还跳直到找到双亲下标保存的值是负数这个下标也就是根了。
把1下标的值加道0下标然后1下标位置保存0下标。 通过以上例子可知并查集一般可以解决一下问题 查找元素属于哪个集合 沿着数组表示树形关系以上一直找到根(即树中中元素为负数的位置)查看两个元素 是否属于同一个集合 沿着数组表示的树形关系往上一直找到树的根如果根相同表明在同一个集合否则不在将两个集 合归并成一个集合 将两个集合中的元素合并 将一个集合名称改成另一个集合的名称集合的个数 遍历数组数组中元素 为负数的个数即为集合的个数。
下面就实现一下并查集~ 名称与编号映射
可能会有这样的问题内部给他们编号万一外面给的是10个人给的是名字我怎么知道谁是那个编号呢怎么解决
借助vectormap建立对应映射关系
vector存储名称列表通过下标快速找到名字。map建立名字到编号的映射关系。
代码示例
templateclass T
class UnionFindSet
{
public:
UnionFindSet(const T* a, size_t sz)
{for (int i 0; i sz; i){_a.push_back(a[i]);//将数组中元素添加到vector中_IndexMap[a[i]] i;//将人映射到hash中}
}private:
vectorT _a; //编号找人
mapT, int _IndexMap; //人找编号
};int main()
{string arr[] { 张三,李四,王五,赵六 };UnionFindSetstring ufs(arr, 4);return 0;
}
_a.push_back(a[i]);这一行代码将数组 a 的第 i 个元素添加到成员变量 _a 向量的末尾。这里 a 是构造函数参数中的一个指针指向传入的数组而 a[i] 则是该数组中第 i 个位置的元素。_IndexMap[a[i]] i;此行代码则是在建立一个映射关系。它使用成员变量 _IndexMap这是一个从类型 T 映射到整数类型的关联容器map。这里它将数组 a 的第 i 个元素作为键i 作为值插入到 _IndexMap 中。因此以后当我们知道某个人的名字时可以通过 _IndexMap 快速查找这个人在原始数组中的索引位置。
这样不管是给下标还是给名字都可以解决这里的问题。 数据结构设计
并查集通过一个数组表示关系
数组下标 表示集合中的元素编号。数组值 用于表示该元素的父节点或根节点的信息。 负数表示集合的根绝对值为该集合中元素的个数。非负数表示其父节点在数组中的下标。
双亲表示法每个节点存储其父节点的位置通过不断向上查找父节点最终可以找到集合的根节点。 2. 并查集基本操作
(1) 初始化
初始时每个元素自成一个集合数组值均为 -1表示每个集合的大小为 1。
UnionFindSet(int sz): _ufs(sz, -1) {} // 初始化大小为 sz每个位置存储 -1 (2) 查询根节点 (FindRoot)
找到某个元素所在集合的根节点。如果当前节点的父节点为负数则该节点是根节点。路径压缩为了提高查询效率将查询路径上的所有节点直接连接到根节点。
int FindRoot(int x) {int root x;// 向上查找根节点while (_ufs[root] 0) {root _ufs[root];//利用上述讲到的特性原则实现向上查找}// 路径压缩while (_ufs[x] 0) {int parent _ufs[x];_ufs[x] root;x parent;}return root;
}
这里在补充说一点并查集 路径压缩 的问题。比如集合是下面这个样子要从9找到根需要跳很多层。影响找根的效率能不能想到什么办法把路径压缩一下呢
其实也很简单 反正都是在同一个集合是不是直接可以考虑把下面的直接压到根的下面做根的孩子。这样就变成了一层。如果数据量很多层数很高压缩路径后这样很不错。
一般在查找根的时候去压缩。查找谁就把它这一条路径压缩。找到根之后判断一下如果它的父亲就是根就不用压缩如果不是说明中间有间隔层然后就可以把这条路径压缩。
比如是这个4首先先把4变成2的孩子然后将4的父亲1也去变成2的孩子这条路径都可以变成2的孩子。 (3) 合并集合 (Union)
并查集 除了路径压缩还有一种提高效率的方式比如两个集合 合并的时候 小集合向大集合合并以减少树的深度。
实现步骤 找到两个集合的根节点。如果根节点相同说明两个元素已在同一个集合中无需合并。否则将小集合的根指向大集合的根并更新集合大小。
bool Union(int x1, int x2) {int root1 FindRoot(x1);int root2 FindRoot(x2);if (root1 root2) return false;// 控制小集合向大集合合并if (abs(_ufs[root1]) abs(_ufs[root2])) {swap(root1, root2);}_ufs[root1] _ufs[root2];_ufs[root2] root1;return true;
} (4) 集合操作总结
查找元素所属集合找到其根节点。判断两个元素是否属于同一集合检查它们的根节点是否相同。统计集合数量统计数组中负数的个数即为集合的数量。 并查集优化
(1) 路径压缩
在查询根节点时将路径上的节点直接连接到根节点减少树的高度。优化后的查找复杂度接近 O(1) 。
(2) 按秩合并
优先将元素较少的集合合并到元素较多的集合进一步减少树的高度。实现方法比较根节点的绝对值选择小集合向大集合合并。
完整代码
#pragma once#includeiostream
#includevector
#includemapusing namespace std;//templateclass T
//class UnionFindSet
//{
//public:
// UnionFindSet(const T* a, size_t sz)
// {
// for (int i 0; i sz; i)
// {
// _a.push_back(a[i]);
// _IndexMap[a[i]] i;
// }
// }
//
//
//private:
// vectorT _a; //编号找人
// mapT, int _IndexMap; //人找编号
//};class UnionFindSet
{
public:UnionFindSet(int sz):_ufs(sz,-1)// 初始时将数组中元素全部设置为1{}bool Union(int x1, int x2){int root1 FindRoot(x1);int root2 FindRoot(x2);// x1已经与x2在同一个集合if (root1 root2)return false;//控制数据量小的往大的集合合并if (abs(_ufs[root1]) abs(_ufs[root2])){swap(root1, root2);}// 将两个集合中元素合并_ufs[root1] _ufs[root2];// 将其中一个集合名称改变成另外一个_ufs[root2] root1;return true;}// 给一个元素的编号找到该元素所在集合的名称int FindRoot(int x){int root x;while (_ufs[root] 0)// 如果数组中存储的是负数找到否则一直继续{root _ufs[root];}//路径压缩while (_ufs[x] 0){int parent _ufs[x];_ufs[x] root;x parent;}return root;}bool IsSet(int x1, int x2){return FindRoot(x1) FindRoot(x2);}// 数组中负数的个数即为集合的个数size_t SetSize(){size_t count 0;for (auto e : _ufs){if (e 0) count;}return count;}private:vectorint _ufs;
};3. 并查集的应用
(1) 统计省份数量
题目链接[LCR 116. 省份数量] 思路 使用并查集将直接连接的城市合并到同一个集合。遍历矩阵统计并查集中集合的数量。
代码实现
int findCircleNum(vectorvectorint isConnected) {int n isConnected.size();vectorint ufs(n, -1);auto Findroot [](int x) {while (ufs[x] 0) {x ufs[x];}return x;};for (int i 0; i n; i) {for (int j i 1; j n; j) {if (isConnected[i][j] 1) {int root1 Findroot(i);int root2 Findroot(j);if (root1 ! root2) {ufs[root1] ufs[root2];ufs[root2] root1;}}}}return count_if(ufs.begin(), ufs.end(), [](int x) { return x 0; });
} (2) 判断等式方程是否成立
题目链接[990. 等式方程的可满足性] 思路 将所有“相等”的变量合并到同一个集合。遍历“不等”关系若两个变量属于同一个集合则矛盾。
代码实现
bool equationsPossible(vectorstring equations) {vectorint ufs(26, -1);auto Findroot [](int x) {while (ufs[x] 0) {x ufs[x];}return x;};// 合并“相等”关系for (auto eq : equations) {if (eq[1] ) {int root1 Findroot(eq[0] - a);int root2 Findroot(eq[3] - a);if (root1 ! root2) {ufs[root1] ufs[root2];ufs[root2] root1;}}}// 检查“不等”关系for (auto eq : equations) {if (eq[1] !) {int root1 Findroot(eq[0] - a);int root2 Findroot(eq[3] - a);if (root1 root2) return false;}}return true;
}
并查集 使用场景两极性的集合划分
连接或不连接相等或不相等 的判断 并查集是一种高效的数据结构支持快速的 合并 和 查询 操作并在路径压缩和按秩合并优化下性能接近常数时间。
