正文 

当前位置： 首页 > 知识 > java教程

数据结构----并查集(代码片段)

4nc414g0n 4nc414g0n     2022-12-03     530

关键词：

并查集

并查集概念

并查集

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

例如有10个元素：
用vector存储：

他们的关系用树形结构表示如下：

在vector中表示如下：

可见：

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

即相当于将子节点的-1值加到父节点的值上

若将8和4合并到一个集合，就是将他们的根节点合并，即：

其vector就变为：

并查集的模拟实现

模拟实现

并查集一般实现：

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

模拟实现：
较简单（略）

  • 注意：两集合合并没有规定必须哪个做根（一般将高度较小的树并入高度较大的树，这样使最终的高度变小，提高平均查找效率）
class UnionFindSet

public:
	UnionFindSet(int size)
		: _set(size, -1)
	
	size_t FindRoot(int x)//判断是否在一个集合，直接复用FindRoot即可
	//此处的x为给定的下标
		while (_set[x] >= 0)
		
			x = _set[x];
		
		return x;//注意返回下标，如无根就返回本身(不是返回_set[x])
	
	bool IsInSet(int x1, int x2)
	
		return (FindRoot(x1) == FindRoot(x2));
	
	void Union(int x1, int x2)
	
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		//这里可以加一层判断，将高度较小的树并入高度较大的树
		if (root1 != root2)
		
			_set[root1] += _set[root2];
			_set[root2] = root1;
		
	
	size_t SetCount()
	
		size_t n = 0;
		for (auto e : _set)
			if (e < 0)
				n++;
		return n;
	
private:
	vector<int> _set;
;

测试：

并查集优化

Union优化

把元素少的集合根节点指向元素多的根节点，能更高概率的生成一个层数比较低的树
较简单，见：并查集 size 的优化

在这里利用元素多的根节点，_set[root]的负值越大，abs()转换为正数进行比较

void Union(int x1, int x2)

	int root1 = FindRoot(x1);//4->1
	int root2 = FindRoot(x2);//8->0
	if (root1 != root2)
	
		if (abs(_set[root1])<abs(_set[root2]))
			swap(root1, root2);
		_set[root1] += _set[root2];
		_set[root2] = root1;

压缩路径

在Find的过程中递归进行路径压缩，找到根就返回，置为根的子节点，路径压缩为1
一般考虑在过程中顺带进行压缩，不一定要一次压缩完成高度为1
如果高度较短不需要压缩

循环

写法1：

size_t FindRoot(int x)//判断是否在一个集合，直接复用FindRoot即可
	//此处的x为给定的下标
		while (_set[x] >= 0)//不为根节点
		
			if(_set[_set[x]]>=0)
				_set[x] = _set[_set[x]];
			x = _set[x];
		
		return x;

写法二：

int 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;

递归 (深度过深有栈溢出的风险)

size_t FindRoot(int x)//判断是否在一个集合，直接复用FindRoot即可
//此处的x为给定的下标
	if (_set[x] >= 0)//不为根节点
	
		_set[x] = FindRoot(_set[x]);//在Find的过程中进行路径压缩，找到根就返回，置为根的子节点，路径压缩为1		
		return _set[x];
	
	else//为根节点
		return x;//注意返回下标(不是返回_set[x])

并查集例题

剑指 Offer II 116. 省份数量
注意：不需要重写一个并查集，直接使用并查集思想

class Solution 
public:
   int findCircleNum(vector<vector<int>>& isConnected) 
       //不需要重写一个并查集，直接使用并查集思想
       vector<int> ufs(isConnected.size(), -1);
       auto find = [&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[0].size();j++)
           
               if(isConnected[i][j] == 1)
               
                   int root1=find(i);
                   int root2=find(j);
                   if(root1!=root2)
                   
                       ufs[root1]+=ufs[root2];
                       ufs[root2]=root1;
                   
               
           
       
       int ret=0;
       for(auto &e:ufs)
       
           if(e<0)
               ret++;
       
       return ret;
   
;

等式方程的可满足性
并查集思想：按照==的表达式构建并查集，再用!=的表达式判断，相悖即false

class Solution 
public:
   bool equationsPossible(vector<string>& equations) 
       vector<int> ufs(26, -1);// 是26个小写字母
       auto find = [&ufs](int x)
       
           while(ufs[x]>=0)
           
               x=ufs[x];
           
           return x;
       ;
       for(auto &str: equations)
       
           if(str[1]=='=')//按照输入建立并查集（==表示集合关系）
           
               int root1 = find(str[0]-'a');
               int root2 = find(str[3]-'a');
               if(root1!=root2)//注意这里是!=
               
                   ufs[root1]+=ufs[root2];
                   ufs[root2]=root1;
               
           
       
       for(auto &str: equations)
       
           if(str[1]=='!')//与输入相悖返回false 
           
               int root1 = find(str[0]-'a');
               int root2 = find(str[3]-'a');
               if(root1==root2)
               
                   return false;
               
           
       
       return true;
   
;

数据结构----并查集(代码片段)

并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归(深度过深有栈溢出的风险)并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每... 查看详情

并查集(代码片段)

...集原理并查集是一种用于处理不相交集合之间合并问题的数据结构，例如求连通子图、判断是否存在环、求最小生成树等。以判断图中是否有环为例，下图是一个无向图。graphTB;A---BA---CA---DC---DC---E首先把每一个顶点都看作是一个... 查看详情

并查集(代码片段)

...合中，即并+查。处理这类问题时便可以用到这种特殊的数据结构，保证了空间时间不会超过限制。并查集是一种抽象的数据结构，其本身不具有结构，必须借助一定的数据结构才能够实现，一般可以用数据，链表和树来实现，... 查看详情

数据结构一篇文章学懂并查集+lrucache，拿来吧你！(代码片段)

...好文建议收藏！！并查集的概念并查集作为一种数据结构在处理需要将n个元素划分成不相交的集合，在逐步 查看详情

数据结构（并查集）(代码片段)

并查集并查集是一种怎么样的数据结构呢？ 1.处理集合合并2.对集合元素进行查找同时并查集对集合元素进行查找的时候，会把路径上所有的点全部都指向父节点，这样就可以把整个查询工作近似的优化成o（1ÿ... 查看详情

数据结构（并查集）(代码片段)

并查集并查集是一种怎么样的数据结构呢？ 1.处理集合合并2.对集合元素进行查找同时并查集对集合元素进行查找的时候，会把路径上所有的点全部都指向父节点，这样就可以把整个查询工作近似的优化成o（1ÿ... 查看详情

数据结构学习--并查集(代码片段)

概念并查集(UnionFind)是一种由孩子指向父亲的树结构，可以高效的处理连接问题(CollectionProblem)。比如：快速判断网络(抽象概念)中节点间的连接状态。对于一组数据，并查集主要支持两个操作：union(p,q);在并查集内... 查看详情

数据结构学习--并查集(代码片段)

概念并查集(UnionFind)是一种由孩子指向父亲的树结构，可以高效的处理连接问题(CollectionProblem)。比如：快速判断网络(抽象概念)中节点间的连接状态。对于一组数据，并查集主要支持两个操作：union(p,q);在并查集内... 查看详情

数据结构学习--并查集(代码片段)

概念并查集(UnionFind)是一种由孩子指向父亲的树结构，可以高效的处理连接问题(CollectionProblem)。比如：快速判断网络(抽象概念)中节点间的连接状态。对于一组数据，并查集主要支持两个操作：union(p,q);在并查集内... 查看详情

[文文殿下]并查集详细解读(代码片段)

初探并查集并查集(Disjoint-Set)是一种优美的数据结构，它擅长动态维护若干交集为空的集合，并且支持快速合并两个集合以及查找某个元素所在的集合。然而这只是并查集所能做的一点微小的工作，文文对并查集的理解是“一种... 查看详情

算法：并查集(代码片段)

...掌握理解算法　　在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（DisjointSets）的合并及查询问题。有一个联合-查找算法（union-findalgorithm）定义了两个用于此数据结构的操作：Find：确定元素属于哪一个子... 查看详情

树--12---并查集(代码片段)

文章目录并查集并查集是一种树型的数据结构并查集结构1.并查集的实现API设计UF(intN)构造方法实现union(intp,intq)合并方法实现代码：测试：案例1:计算机网诺连接2.UF_Tree算法优化eleAndGourp数组API设计find(intp)查询方法实现unio... 查看详情

树的应用——并查集及实现代码(代码片段)

...—合并并查集的用途什么是并查集 并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。常常在使用中以森林来表示。 并查集支持以下3种操作：初始化（Initial）... 查看详情

带权并查集&&并查集(代码片段)

...集合初始化为其自身。通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。voidinit(intn)for(inti=1;i<=n;i++)q[i]=i; 查找查找元素 查看详情

解决动态连通性——并查集(代码片段)

...lip;…唉 　　什么是并查集？并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。在实际解决问题的过程中并查集的应用广泛，但主要还是用来判断两点是否联通，以... 查看详情

并查集(代码片段)

...其间要反复查找一个元素在哪个集合中。它是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。常常在使用中以森林来表示。　　并查集有两种实现方式，一种是路径压缩O(1)，第二种是按秩合并O(... 查看详情

什么是并查集？建议收藏(代码片段)

...b一文彻底搞懂《并查集》！概念并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否 查看详情

并查集详解(代码片段)

先上维基百科并查集是一种树型的数据结构，用于处理一些不交集（DisjointSets）的合并及查询问题有一个联合-查找算法（union-findalgorithm）定义了两个用于此数据结构的操作Find：确定元素属于哪一个子集。它可以被用来确定两个... 查看详情