软件网站开发市场前景,公司网站自己怎么建立,注册功能网站建设,php网站接口开发文章目录 前言举例#xff1a; 一、1.构造函数2.查找元素属于哪个集合FindRoot3.将两个集合归并成一个集合Union4.查找集合数量SetCount 二、源码 前言
需要将n个不同的元素划分成一些不相交的集合。开始时#xff0c;每个元素自成一个单元素集合#xff0c;然后按一定的规… 文章目录 前言举例 一、1.构造函数2.查找元素属于哪个集合FindRoot3.将两个集合归并成一个集合Union4.查找集合数量SetCount 二、源码 前言
需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
举例
学生小分队s1{0,6,7,8}成都学生小分队s2{1,4,9}武汉学生小分队s3{2,3,5}就相互认识了10个人形成了三个小团体。假设右三个群主0,1,2担任队长负责大家的出行。 西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起两个 小圈子的学生相互介绍最后成为了一个小圈子 仔细观察数组中内融化可以得出以下结论 数组的下标对应集合中元素的编号数组中如果为负数负号代表根数字代表该集合中元素个数数组中如果为非负数代表该元素双亲在数组中的下标 一、
1.构造函数
UnionFindSet(size_t size):_set(size,-1)//数组中初始化为-1//数组的下标对应集合中元素的编号//数组的内容如果是非负数代表这个元素的根的下标//数组内容为负数代表这个数字为根绝对值为这棵树的大小{}2.查找元素属于哪个集合FindRoot
size_t FindRoot(int x) {//. 查找元素属于哪个集合while (_set[x] 0) {x _set[x];}//找到非负的数这个数的下标即为根的下标return x;}3.将两个集合归并成一个集合Union
void Union(int x1, int x2) {//将两个集合归并同一个集合//将元素x2合并进x1int root1 FindRoot(x1);int root2 FindRoot(x2);if (root1 ! root2) {//保证两个元素不在同一个集合中_set[root1] _set[root2];// x2根的内容为负数绝对值为这棵树的数量//把x2归并到x1所在集合中//x1所在集合的大小发生变化_set[root2] root1;//x2的根发生变化}}4.查找集合数量SetCount
size_t SetCount() {//统计集合数量有多少棵树int count 0;for (size_t i 0; i _set.size(); i) {if (_set[i] 0) {count;}}//负数的数量即根的数量即集合的数量return count;}二、源码
class UnionFindSet {
public:UnionFindSet(size_t size):_set(size,-1)//数组中初始化为-1//数组的下标对应集合中元素的编号//数组的内容如果是非负数代表这个元素的根的下标//数组内容为负数代表这个数字为根绝对值为这棵树的大小{}size_t FindRoot(int x) {//. 查找元素属于哪个集合while (_set[x] 0) {x _set[x];}//找到非负的数这个数的下标即为根的下标return x;}void Union(int x1, int x2) {//将两个集合归并同一个集合//将元素x2合并进x1int root1 FindRoot(x1);int root2 FindRoot(x2);if (root1 ! root2) {//保证两个元素不在同一个集合中_set[root1] _set[root2];// x2根的内容为负数绝对值为这棵树的数量//把x2归并到x1所在集合中//x1所在集合的大小发生变化_set[root2] root1;//x2的根发生变化}}size_t SetCount() {//统计集合数量有多少棵树int count 0;for (size_t i 0; i _set.size(); i) {if (_set[i] 0) {count;}}//负数的数量即根的数量即集合的数量return count;}private:vectorint _set;};
