【高阶数据结构】——并查集

这篇具有很好参考价值的文章主要介绍了【高阶数据结构】——并查集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

并查集的原理

在一些应用问题中,需要将n个不同的元素划分成一些不相交的集合。开始时,每个元素自成一个单元素集合, 然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为 并查集(union-find set)

并查集建立映射关系的一种方法:

template <class T>
class UnionFindSet
{
public:
	UnionFindSet(const T* a, size_t n)
	{
		for (size_t i = 0; i < n; i++)
		{
			// 建立映射关系
			_a.push_back(a[i]);
			_indexMap[a[i]] = i;
		}
	}
private:
	vector<T> _a; //编号找人
	map<T, int> _indexMap; //人找编号
};

【高阶数据结构】——并查集,数据结构,数据结构,算法

举个栗子:

比如:某公司今年校招全国总共招生10人,西安招4人,成都招3人,武汉招3人,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担任队长,负责大家的出行。

【高阶数据结构】——并查集,数据结构,数据结构,算法

一趟火车之旅后,每个小分队成员就互相熟悉,称为了一个朋友圈。

【高阶数据结构】——并查集,数据结构,数据结构,算法

从上图可以看出:编号6,7,8同学属于0号小分队,该小分队中有4人(包含队长0);编号为4和9的同学属于1号小分队,该小分队有3人(包含队长1),编号为3和5的同学属于2号小分队,该小分队有3个人(包含队长1)。仔细观察数组中内融化,可以得出以下结论:

  1. 数组的下标对应集合中元素的编号
  2. 数组中如果为负数,负号代表根,数字代表该集合中元素个数
  3. 数组中如果为非负数,代表该元素双亲在数组中的下标

【高阶数据结构】——并查集,数据结构,数据结构,算法

现在0集合有7个人,2集合有3个人,总共两个朋友圈。

通过以上例子可知,并查集一般可以解决一下问题:

  1. 查找元素属于哪个集合
    沿着数组表示树形关系以上一直找到根(即:树中中元素为负数的位置)
  2. 查看两个元素是否属于同一个集合
    沿着数组表示的树形关系往上一直找到树的根,如果根相同表明在同一个集合,否则不在
  3. 将两个集合归并成一个集合
    将两个集合中的元素合并
    将一个集合名称改成另一个集合的名称
  4. 集合的个数
    遍历数组,数组中元素为负数的个数即为集合的个数。

并查集的实现

class UnionFindSet
{
public:
	UnionFindSet(int size)
		:_set(size, -1)
	{}

	//查询
	size_t FindRoot(int x)
	{
		int root = x;
		while (_set[root] >= 0)
		{
			root = _set[root];
		}

		//压缩路径(优化)
		while (_set[x] >= 0)
		{
			int parent = _set[x];
			_set[x] = root;
			x = parent;
		}

		return root;
	}

	//合并两个集合
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		if (root1 != root2) //不属于一个集合,将二者合并
		{
			//将节点少的集合合并到节点多的集合当中(优化)
			if (abs(_set[root1]) < abs(_set[root2]))
				swap(root1, root2);

			_set[root1] += _set[root2];
			_set[root2] = root1;
		}
	}
	
	// 判断x1和x2是否在同一个集合中
	bool Insert(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}
	
	//查看set中有多少对集合
	size_t SetCount()
	{
		size_t cnt = 0;
		for (auto e : _set)
			if (e < 0) cnt++;
		return cnt;
	}

private:
	vector<int> _set;
};

并查集的应用

💕 省份数量

【高阶数据结构】——并查集,数据结构,数据结构,算法

//并查集代码
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFindSet ufs(isConnected.size());
        for(size_t i = 0; i < isConnected.size(); i++)
        {
            for(size_t j = 0; j < isConnected[i].size(); j++)
            {
                if(isConnected[i][j] == 1)
                    ufs.Union(i,j);
            }
        }
        return ufs.SetCount();
    }
};

当我们没有实现并查集时,其实也是可以直接使用数组模拟的。

class Solution {
public:
    size_t FindRoot(int x)
    {
        while(ufs[x] >= 0)
        {
            x = ufs[x];
        }
        return x;
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        ufs.resize(isConnected.size(), -1);
        for(int i = 0; i < isConnected.size(); i++)
        {
            for(int j = 0; j < isConnected[i].size(); j++)
            {
                if(isConnected[i][j] == 1)
                {
                    int root1 = FindRoot(i);
                    int root2 = FindRoot(j);
                    if(root1 != root2)
                    {
                        if(abs(ufs[root1]) < abs(ufs[root2]))
                            swap(root1, root2);
                        ufs[root1] += ufs[root2];
                        ufs[root2] = root1;
                    }
                }
            }
        }
        int cnt = 0;
        for(auto& e : ufs)
            if(e < 0) cnt++;
        return cnt;            
    }
private:
    vector<int> ufs;
};

💕 等式方程的可满足性

【高阶数据结构】——并查集,数据结构,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-579216.html

class Solution {
public:
    int Find(int x)
    {
        while(ufs[x] >= 0)
            x = ufs[x];
        return x;
    }
    bool equationsPossible(vector<string>& equations) {
        ufs.resize(26, -1);
        for(auto& str : equations)
        {
            if(str[1] == '=')
            {
                int root1 = Find(str[0]-'a');
                int root2 = Find(str[3]-'a');
                if(root1 != root2)
                {
                    if(abs(ufs[root1]) < abs(ufs[root2]))
                        swap(root1, root2);
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }
        for(auto& str : equations)
        {
            if(str[1] == '!')
            {
                int root1 = Find(str[0]-'a');
                int root2 = Find(str[3]-'a');
                if(root1 == root2)
                    return false;
            }
        }
        return true;
    }
private:
    vector<int> ufs;
};

到了这里,关于【高阶数据结构】——并查集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    链表题目:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 AcWing. 826.单链表 双链表 AcWing 827.双链表 AcWing 828.模拟栈 AcWing 3302.表达式求值 AcWing 829. 模拟队列 AcWing 830.单调栈 AcWing 154.滑动窗口 AcWing 831. KMP字符串 AcWing 835. Trie字符串统计 AcWing 143. 最大异或对 AcWing 836.合并集合

    2024年02月15日
    浏览(48)
  • 数据结构--并查集

    所有元素的全集s 将各个元素划分为若干个互不相交的子集 用一个数组S[ ]即可表示“集合”关系 集合的两个基本操作―— “并” color{red}“并” “ 并 ” 和 “查” color{red}“查” “ 查 ” Find -—“查”操作:确定一个指定元素所属集合 Union --“并”操作:将两个不想交的集

    2024年02月15日
    浏览(36)
  • 数据结构---并查集

    这里可以使用生活中的一个例子来带着大家理解并查集,大家在上学的过程中肯定会发现一种现象,在开学之前大家谁也不认识谁每个人都是一个小团体,可是开学之后因为座位旁边有一个同桌,所以开学没多久你和同桌就会互相认识并且开心的玩在一起,那么这时就是两个

    2024年02月15日
    浏览(40)
  • 【数据结构】并查集

    并查集是简单的数据结构,学会并查集,为图打好基础。 是树状的数据结构,用于处理相交集合的合并与查询 通常用森林表示,一片森林表示一个集合 并查集一般需要完成 查找元素属于哪个集合 查看两个元素是否属于同一个集合 将两个集合归并成一个集合 集合的个数 假

    2024年02月19日
    浏览(35)
  • 【数据结构】--并查集

    目录 一、概念 ​编辑 二、应用场景--“连接”问题(属于同一Qu 三、实现思路  四、如何存储数据 五、定义接口 1.初始化(init) 2.其他 isSame() 六、抽象类 六、Quick Find【v1 所在集合的所有元素都指向 v2 的根节点】 1.Union 1.Union图解 2.注意点:  3.代码实现 2.find  1.find图

    2023年04月09日
    浏览(31)
  • 数据结构详细笔记——并查集

    集合:将各个元素划分为若干个互不相交的子集的集合 森林是m(m=0)棵互不相交的树的集合 优化思路:在每次Union操作构建树的时候,尽可能让树不长高 ①用根结点的绝对值表示树的结点的总数 ②Union操作,让小树合并到大树 优化思路:先找到根结点,再将查找路径上所有结

    2024年02月06日
    浏览(38)
  • 数据结构之并查集

    并查表原理是一种 树型的数据结构 ,用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林(parent),树的根节点唯一标识了一个集合,我们只要找到了某个元素的树根,就能确定它在哪个集合里。这类问题的抽象数据类型称为并查集(uni

    2024年02月12日
    浏览(36)
  • 【数据结构】| 并查集及其优化实现

    以一个直观的问题来引入并查集的概念。 亲戚问题:有一群人,他们属于不同家族,同一个家族里的人互为亲戚,不同家族的人不是亲戚。随机指定两个人,问他们是否有亲戚关系。 以下图3个不相交的集合表示 3 个家族,当询问两个人是否有亲戚关系时,也就是问两个元素

    2024年02月09日
    浏览(37)
  • 数据结构(八):并查集详解 (多图+动图)

    目录 一、什么是并查集 二、并查集的存储结构 三、并查集的基本操作 (一)初始化 (二)Find操作 (三)Union操作 四、并查集的优化 (一)Union操作优化(小树并入大树) (二)Find操作优化(压缩路径)         并查集的逻辑结构是一个包含N个元素的 集合 ,如图:

    2024年02月03日
    浏览(42)
  • 计算机基础--->数据结构(9)【并查集】

    并查集是一种用于解决集合合并和查询问题的数据结构,主要用于实现有关集合的操作,它有两种主要操作,合并(union)和查找(find)。 查找(Find):用来确定元素属于哪个集合。它接受一个元素作为参数,并返回这个元素所属集合的代表元素。通过查找操作,可以判断

    2024年02月15日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包