智能墨韵书生

这个屌丝很懒，什么也没留下！

热门标签

并查集（高阶数据结构）

作者：智能墨韵书生 | 2024-02-02 12:00:13

踩

并查集（高阶数据结构）

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题
并查集通常用森林来表示，森林中的每棵树表示一个集合，树中的结点对应一个元素

说明： 虽然利用其他数据结构也能完成不相交集合的合并及查询，但在数据量极大的情况下，其耗费的时间和空间极大

一、并查集的原理

以朋友圈为例，现在有10个人（从0开始编号），刚开始这10个人互不认识，各自属于一个集合

并查集会用一个数组来表示这10个人之间的关系，数组的下标对应就是这10个人的编号，刚开始时数组中的元素都初始化为-1

说明：数组中某个位置的值为负数，表示该位置是树的根，这个负数的绝对值表示的这棵树（集合）中数据的个数，因为刚开始每个人各自属于一个集合，所以将数组中的位置都初始化为-1

后来这10个人之间通过相互认识，最终形成了三个朋友圈

此时并查集数组中各个位置的值如下

说明：数组中某个位置的值为非负数，表示该位置不是树的根，这个非负数的值就是这个结点的父结点的编号

后来4号和8号又通过某种机遇互相认识了，这时其所在的两个集合就需进行合并，最终就变成了两个朋友圈

在根据两个元素合并两个集合时，需先分别找到这两个元素所在集合的根结点，然后再将一个集合合并到另一个集合，并且合并后需要更新数组中根结点的值

合并集合找根结点的原因：

若这两个元素所在集合的根结点相同，说明这两个元素本身就在同一个集合，无需合并
合并集合后需要更新这两个集合的根结点的值

二、并查集的实现

实现并查集时通常会实现如下接口：

初始化并查集
查找元素所在的集合
判断两个元素是否在同一个集合
合并两个元素所在的集合
获取并查集中集合的个数


#include <iostream>
#include <vector>
using namespace std;
 
class UnionFindSet
{
public:
	// 构造函数
	UnionFindSet(size_t size);
	// 查找元素所在的集合
	int FindRoot(int value);
	// 判断两个元素是否在同一个集合
	bool IsSameSet(int value1, int value2);
	// 合并两个元素所在的集合
	bool Union(int value1, int value2);
	// 获取并查集中集合的个数
	size_t GetSetSize();
private:
	vector<int> _ufs; //维护各个结点间的关系
};

并查集中的数组：

数组的下标依次对应每个元素的编号
数组中元素值为负数，表示下标编号元素为根结点，负数的绝对值表示该集合中元素的个数
数组中元素值为非负数，表示下标编号元素的父结点的编号

2.1 并查集的初始化

并查集中会用一个数组来维护各个结点之间的关系，在初始化并查集时，根据元素的个数开辟数组空间，并将数组中的元素初始化为-1即可

UnionFindSet(size_t size): _ufs(size, -1) {}

2.2 查找元素所在的集合

查找元素所在的集合，本质就是查找元素所在集合的根结点

查找逻辑如下：

若元素对应下标位置存储的是负数，则说明该元素即为根结点，返回该元素即可
若元素对应下标位置存储的是非负数，则跳转到其父结点的位置继续查找根结点

迭代方式实现：


int FindRoot(int value)
{
	int root = value;
	while (_ufs[root] >= 0) 
        root = _ufs[root];
	return root;
}

递归方式实现：


int FindRoot(int x) {
	return _ufs[x] < 0 ? x : FindRoot(_ufs[x]);
}

2.3 判断两个元素是否在同一个集合

要判断两个元素是否在同一个集合，本质就是判断这两个元素所在集合的根结点是否相同


bool IsSameSet(int value1, int value2) {
	return FindRoot(value1) == FindRoot(value2);
}

2.4 合并两个元素所在的集合

合并逻辑如下：

分别找到两个元素所在集合的根结点
若这两个元素所在集合的根结点相同，则无需合并。若这两个元素所在集合的根结点不同，则将小集合合并到大集合上
将小集合根结点的值累加到大集合的根结点上，使得大集合根结点的值的绝对值等于两个集合中元素的总数。
将小集合根结点的值改为大集合根结点的编号，即将小集合的根结点作为大集合根结点的孩子，使得两个集合变为一个集合


bool Union(int value1, int value2)
{
	int root1 = FindRoot(value1), root2 = FindRoot(value2);
	//本身在同一个集合,不需合并
	if (root1 == root2) return false;
	//合并操作: 数据量小的 往 数据量大的 合并
	if (abs(_ufs[root1]) < abs(_ufs[root2])) swap(root1, root2);
	_ufs[root1] += _ufs[root2];
	_ufs[root2] = root1;
	return true;
}

说明：当两个集合合并时，尽量将小集合合并到大集合上，因为被合并的那个集合中的所有结点在合并后层数都会加一，所以这样做的目的就是为了让较少的结点层数加一，该操作不是必须的

2.5 获取并查集中集合的个数

获取并查集中集合的个数，本质就是统计数组中负值（根结点）的个数


size_t GetSetSize()
{
	size_t count = 0;
	for (int i = 0; i < _ufs.size(); ++i)
		if (_ufs[i] < 0) ++count;
	return count;
}

2.6 并查集的路径压缩

当数据量很大的时候，并查集中树的层数可能会变得很高，这时查找一个元素所在集合的根结点时就需要往上走很多层，此时可以考虑进行路径压缩

路径压缩一般会在查找根结点时进行，当根据一个结点查找其根结点时，该路径上所有的结点都会被压缩，最终这些结点会直接被挂在根结点下，下次再根据这些结点查找根结点时就能快速找到根结点

迭代方式实现：


int FindRoot(int value)
{
	int root = value;
	while (_ufs[root] >= 0) root = _ufs[root];
	//路径压缩
	while (_ufs[value] >= 0)
	{
		int parent = _ufs[value];
		_ufs[value] = root;
		value = parent;
	}
	return root;
}

递归方式实现：


int FindRoot(int x) 
{
	int parent = x; //默认当前结点就是根结点
	if (_ufs[x] >= 0) { //当前结点值不是负数则继续向上找
		parent = FindRoot(_ufs[x]); //找到根结点
		_ufs[x] = parent; //将当前结点的父亲改为根结点（路径压缩）
	}
	return parent;
}

2.7 元素的编号问题

上面在实现并查集时，默认元素的编号都是从0开始依次递增的，但用户所给的编号可能并不是从0开始的，也不是连续的，甚至可能不是数字

可以用模板的方式来实现并查集：

在初始化并查集时，根据所给元素建立元素与数组下标之间的映射关系。
在查找元素所在集合的根结点时，先根据所给元素得到其对应的数组下标，然后再进行查找


#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
 
template<class T>
class UnionFindSet
{
public:
	// 构造函数
	UnionFindSet(const vector<T>& v): _ufs(v.size(), -1) 
	{
		for (int i = 0; i < v.size(); ++i)
			_indexMap[v[i]] = i;
	}
	
	// 查找元素所在的集合
	int FindRoot(const T& value)
	{
		int root = _indexMap[value];
		while (_ufs[root] >= 0) root = _ufs[root];
		//路径压缩
		int tmp = _indexMap[value];
		while (_ufs[tmp] >= 0) {
			int parent = _ufs[tmp];
			_ufs[tmp] = root;
			tmp = parent;
		}
		return root;
	}
 
	// 判断两个元素是否在同一个集合
	bool IsSameSet(const T& value1, const T& value2) {
		return FindRoot(value1) == FindRoot(value2);
	}
 
	// 合并两个元素所在的集合
	bool Union(const T& value1, const T& value2)
	{
		int root1 = FindRoot(value1), root2 = FindRoot(value2);
		//本身在同一个集合,不需合并
		if (root1 == root2) return false;
		//合并操作: 数据量小的 往 数据量大的 合并
		if (abs(_ufs[root1]) < abs(_ufs[root2])) swap(root1, root2);
		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
		return true;
	}
 
	// 获取并查集中集合的个数
	size_t GetSetSize()
	{
		size_t count = 0;
		for (int i = 0; i < _ufs.size(); ++i)
			if (_ufs[i] < 0) ++count;
		return count;
	}
private:
	vector<int> _ufs; //维护各个结点间的关系
	unordered_map<T, int> _indexMap;//维护元素与下标之间的映射关系
};

再使用并查集时就可以传入任意类型的元素了


int main() 
{
	vector<string> v = { "张三", "李四", "王五", "赵六", "田七", "周八", "吴九" };
 
	UnionFindSet<string> ufs(v);
	cout << ufs.GetSetSize() << endl; //7
 
	ufs.Union("张三", "李四");
	ufs.Union("王五", "赵六");
	cout << ufs.GetSetSize() << endl; //5
 
	ufs.Union("张三", "赵六");
	cout << ufs.GetSetSize() << endl; //4
 
	return 0;
}

三、并查集题目

3.1 省份的数量

LCR 116. 省份数量 - 力扣（LeetCode）


class Solution 
{
public:
    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        vector<int> ufs(isConnected.size(), -1);
        auto findRoot = [&ufs](int value) {
            while(ufs[value] >= 0) value = ufs[value];
            return value;
        };
        auto getSetSize = [&ufs]() {
            size_t count = 0;
            for(int i = 0; i < ufs.size(); ++i)
                if(ufs[i] < 0) ++count;
            return count;
        };
        for(size_t i = 0; i < isConnected.size(); ++i)
            for(size_t j = 0; j < isConnected[0].size(); ++j)
                if(isConnected[i][j] == 1) 
                {
                    int root1 = findRoot(i);
                    int root2 = findRoot(j);
                    if(root1 != root2) 
                    {
                        ufs[root1] += ufs[root2];
                        ufs[root2] = root1;
                    }
                }
        return getSetSize();
    }
};

3.2 等式方程的可满足性

990. 等式方程的可满足性 - 力扣（LeetCode）


class Solution {
public:
    bool equationsPossible(vector<string>& equations) 
    {
        vector<int> ufs(26, -1);
        auto findRoot = [&ufs](int value) {
            while(ufs[value] >= 0) value = ufs[value];
            return value;
        };
        //第一遍,先把相等的值合并到一个集合中
        for(auto& str : equations)
        {
            if(str[1] == '=')
            {
                int root1 = findRoot(str[0] - 'a');
                int 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');
                int root2 = findRoot(str[3] - 'a');
                if(root1 == root2) return false;
            }
        }
        return true;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/55249