【高效管理集合】并查集的实现与应用-LMLPHP

并查集的概念

并查集,也称为不相交集,是一种树形的数据结构,用于处理一些不相交集合的合并及查询问题。简单来说,它主要用于处理元素分组的问题。

主要操作

  1. 查找(Find)
    确定元素所属的集合,通常返回该元素的根节点。

  2. 合并(Union)
    将两个集合合并为一个集合。

优化技术

  • 路径压缩
    在查找操作中,将访问路径上的节点直接连接到根节点,以减少树的高度。

  • 按秩合并
    总是将较小的树合并到较大的树下,以保持树的平衡。

应用场景

并查集广泛用于以下问题:

  • 判断两个元素是否在同一集合中。
  • 合并两个集合。
  • 最小生成树算法。
  • 网络连接问题等。

这种数据结构在许多算法中都非常有效,尤其是在处理集合合并和查询时。

并查集的实现

基本框架

class UnionFindset
{
public:
	UnionFindset(size_t n)
	{}
	//合并接口
	void Union(int x1, int x2)
	{
	}
	//找根的位置
	int FindRoot(int x)
	{
	}
	//是否在相同一个集合
	bool IsInSet(int x1, int x2)
	{
	}
	//并查集中有多少个集合
	size_t SetSize()
	{
	}
	//压缩路径
	void findWithPathCompression()
	{
	}
private:
	//下标---->人
	vector<int> _ufs;
};

【高效管理集合】并查集的实现与应用-LMLPHP

并查集的主要接口

构造函数:
【高效管理集合】并查集的实现与应用-LMLPHP

UnionFindset(size_t n)
	//将每个位置初始化为-1
	:_ufs(n, -1)
{}

将每个位置初始化为-1,在并查集中存储的大于零的数表示的是父亲的下标,存储的小于0的值表示的是根节点。
索引根的位置:

//找根的位置
int FindRoot(int x)
{
	int parent = x;
	//索引根的位置
	while (_ufs[parent] > 0) parent = _ufs[parent];
	return parent;
}

当下标对应的数是负数的时候,当前位置就是根。
合并不相关集合:

//合并接口
void Union(int x1, int x2)
{
	int parent1 = FindRoot(x1), parent2 = FindRoot(x2);
	//本身就在一个集合就不需要进行合并
	if (parent1 == parent2) return;
	if (parent1 > parent2) swap(parent1, parent2);
	else
	{
		_ufs[parent1] += _ufs[parent2];
		//索引下标
		_ufs[parent2] = parent1;
	}
}

合并两个不相关集合,只需要先找到根,复用上面的接口,然后将这两个集合的根进行合并即可,将任意一个根对应的数加到另一个数的根上,然后将这个跟的下标改为另一个根的下标即可,就完成了合并了。
判断是否在同一集合:
只需要判断两个节点的根是否相同即可。

//是否在相同一个集合
bool IsInSet(int x1, int x2)
{
	return FindRoot(x1) == FindRoot(x2);
}

查看有多少个集合:
只需要查看数组中有多少个小于0的位置即可。

//并查集中有多少个集合
size_t SetSize()
{
	size_t size = 0;
	for (size_t i = 0;i < _ufs.size();i++)
		if (_ufs[i] < 0)size++;
	return size;
}

压缩路径:

int FindWithPathCompression(int x)
{
    if (_ufs[x] < 0)
    {
        return x; // 找到根节点
    }
    // 递归查找根节点,并进行路径压缩
    _ufs[x] = FindWithPathCompression(_ufs[x]);
    return _ufs[x]; // 返回根节点
}

总体代码

class UnionFindset
{
public:
	UnionFindset(size_t n)
		//将每个位置初始化为-1
		:_ufs(n, -1)
	{}
	//合并接口
	void Union(int x1, int x2)
	{
		int parent1 = FindRoot(x1), parent2 = FindRoot(x2);
		//本身就在一个集合就不需要进行合并
		if (parent1 == parent2) return;
		if (parent1 > parent2) swap(parent1, parent2);
		else
		{
			_ufs[parent1] += _ufs[parent2];
			//索引下标
			_ufs[parent2] = parent1;
		}
	}
	//找根的位置
	int FindRoot(int x)
	{
		int parent = x;
		//索引根的位置
		while (_ufs[parent] > 0) parent = _ufs[parent];
		return parent;
	}
	//是否在相同一个集合
	bool IsInSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}
	//并查集中有多少个集合
	size_t SetSize()
	{
		size_t size = 0;
		for (size_t i = 0;i < _ufs.size();i++)
			if (_ufs[i] < 0)size++;
		return size;
	}
	//压缩路径
	int FindWithPathCompression(int x)
	{
	    if (_ufs[x] < 0)
	    {
	        return x; // 找到根节点
	    }
	    // 递归查找根节点,并进行路径压缩
	    _ufs[x] = FindWithPathCompression(_ufs[x]);
	    return _ufs[x]; // 返回根节点
	}
private:
	//下标---->人
	vector<int> _ufs;
};

并查集的应用

省份的数量

题目信息:

示例:

代码展示:

class Solution 
{
public:
    //给的是城市的下标
    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        //vector模拟并查集行为
        vector<int> ufs(isConnected.size(),-1);
        //需要用引用进行捕获
        auto FindRoot=[&ufs](int x){
            while(ufs[x]>=0) x=ufs[x];
            return x;
        };
        //遍历二维数组
        for(size_t i=0;i<isConnected.size();i++)
        {
            for(size_t j=0;j<isConnected[i].size();j++)
            {
                //如果这两个城市相连,就进入一个集合
                if(isConnected[i][j]==1)
                {
                    int root1=FindRoot(i),root2=FindRoot(j);
                    if(root1!=root2)
                    {
                        //将两个合并
                        ufs[root1]+=ufs[root2];
                        //存父亲的下标
                        ufs[root2]=root1;
                    }
                }
            }
        }
        int n=0;
        for(auto e:ufs)
            if(e<0)n++;
        return n;
    }
};

等式方程的可满足性

题目信息:

示例:

代码展示:

class Solution 
{
public:
    bool equationsPossible(vector<string>& equations) 
    {
        //开26个空间
        vector<int> ufs(26,-1);
        auto FindRoot=[&ufs](int x){
            while(ufs[x]>=0) x=ufs[x];
            return x;
        };
        //第一遍找相等的字母
        for(auto& str:equations)
        {
            if(str[1]=='=')
            {
                int root1=FindRoot(str[0]-'a'),root2=FindRoot(str[3]-'a');
                if(root1!=root2)
                {
                    ufs[root1]+=ufs[root2];
                    ufs[root2]=root1;
                }
            }
        }
        //第二遍找不同的字母,如果不同的字母在一个集合中,返回false
        for(auto& str:equations)
        {
            if(str[1]=='!')
            {
                int root1=FindRoot(str[0]-'a'),root2=FindRoot(str[3]-'a');
                if(root1==root2) return false;
            }
        }
        return true;
    }
};

总结

并查集(Union-Find)是一种高效的数据结构,广泛应用于解决动态连通性问题。通过支持合并和查找操作,并查集能够有效管理和查询集合关系。其核心优化技术——路径压缩和按秩合并,显著提高了操作的效率,使得在大规模数据处理时依然保持良好的性能。

在实际应用中,理解并掌握并查集的原理和实现方式,能够帮助开发者解决许多复杂问题,如图论算法、网络连接等。通过本次介绍,希望能对并查集的概念和应用提供一个清晰的认识,为进一步的学习和实践打下基础。

10-02 23:21