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

用户11305458

发布于 2024-10-09 17:28:38

1060

发布于 2024-10-09 17:28:38

文章被收录于专栏：学习

并查集的概念

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

主要操作

查找（Find） 确定元素所属的集合，通常返回该元素的根节点。
合并（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;
};

并查集的主要接口

构造函数：

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