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

并查集

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

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

并查集的原理

并查集的原理

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

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

说明一下：

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

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

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

说明一下：

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

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

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

示意图如下：

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

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

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

并查集的实现

并查集的实现

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

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

代码如下：

//并查集
class UnionFindSet {
public:
	//构造函数
	UnionFindSet(int n);
	//查找元素所在的集合
	int findRoot(int x);
	//判断两个元素是否在同一个集合
	bool inSameSet(int x1, int x2);
	//合并两个元素所在的集合
	bool unionSet(int x1, int x2);
	//获取并查集中集合的个数
	int getNum();
private:
	vector<int> _ufs; //维护各个结点之间的关系
};

并查集中的数组：

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

并查集的初始化

并查集的初始化

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

代码如下：

//构造函数
UnionFindSet(int n)
	:_ufs(n, -1) //初始时各个元素自成一个集合
{}

查找元素所在的集合

查找元素所在的集合

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

查找逻辑如下：

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

迭代方式实现如下：

//查找元素所在集合的根结点（迭代）
int findRoot(int x) {
	int parent = x; //默认当前结点就是根结点
	while (_ufs[parent] >= 0) { //当前结点值不是负数则继续向上找
		parent = _ufs[parent];
	}
	return parent; //返回根结点
}

递归方式实现如下：

//查找元素所在集合的根结点（递归）
int findRoot(int x) {
	return _ufs[x] < 0 ? x : findRoot(_ufs[x]);
}

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

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

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

代码如下：

//判断两个元素是否在同一个集合
bool inSameSet(int x1, int x2) {
	return findRoot(x1) == findRoot(x2);
}

合并两个元素所在的集合

合并两个元素所在的集合

合并逻辑如下：

1. 分别找到两个元素所在集合的根结点。
2. 如果这两个元素所在集合的根结点相同，则无需合并，如果这两个元素所在集合的根结点不同，则将小集合合并到大集合上。
3. 将小集合根结点的值累加到大集合的根结点上，使得大集合根结点的值的绝对值等于两个集合中元素的总数。
4. 将小集合根结点的值改为大集合根结点的编号，也就是让小集合的根结点作为大集合根结点的孩子，使得两个集合变为一个集合。

代码如下：

//合并两个元素所在的集合
bool unionSet(int x1, int x2) {
	int parent1 = findRoot(x1), parent2 = findRoot(x2); //分别找到两个元素所在集合的根结点
	if (parent1 == parent2) //两个结点已经位于同一集合
		return false;
	if (_ufs[parent1] > _ufs[parent2]) //让parent1标记大集合根结点，parent2标记小集合根结点
		swap(parent1, parent2);
	//将小集合合并到大集合上
	_ufs[parent1]  = _ufs[parent2]; //将小集合根结点的值累加到大集合的根结点上
	_ufs[parent2] = parent1; //将小集合根结点的值改为大集合根结点的编号
	return true;
}

说明一下：

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

获取并查集中集合的个数

获取并查集中集合的个数

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

代码如下：

//获取并查集中集合的个数
int getNum() {
	int count = 0; //统计根结点的个数
	for (const int& val : _ufs) {
		if (val < 0) //元素值为负数则为根结点
			count  ;
	}
	return count; //返回根结点的个数
}

并查集的路径压缩

并查集的路径压缩

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

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

迭代方式实现如下：

//查找元素所在集合的根结点（迭代）
int findRoot(int x) {
	int root = x; //默认当前结点就是根结点
	while (_ufs[root] >= 0) { //当前结点值不是负数则继续向上找
		root = _ufs[root];
	}
	//路径压缩
	while (_ufs[x] >= 0) { //遍历从根结点到x结点路径上的所有结点
		int parent = _ufs[x];
		_ufs[x] = root; //将结点的父亲改为根结点
		x = parent;
	}
	return root; //返回根结点
}

递归方式实现如下：

//查找元素所在集合的根结点（递归）
int findRoot(int x) {
	int parent = x; //默认当前结点就是根结点
	if (_ufs[x] >= 0) { //当前结点值不是负数则继续向上找
		parent = findRoot(_ufs[x]); //找到根结点
		_ufs[x] = parent; //将当前结点的父亲改为根结点（路径压缩）
	}
	return parent; //返回根结点
}

元素的编号问题

元素编号问题

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

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

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

代码如下：

//并查集
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& x) {
		int parent = _indexMap[x]; //默认当前结点就是根结点
		while (_ufs[parent] >= 0) { //当前结点值不是负数则继续向上找
			parent = _ufs[parent];
		}
		return parent; //返回根结点
	}
	//合并两个元素所在的集合
	bool unionSet(const T& x1, const T& x2) {
		int parent1 = findRoot(x1), parent2 = findRoot(x2); //分别找到两个元素所在集合的根结点
		if (parent1 == parent2) //两个结点已经位于同一集合
			return false;
		if (_ufs[parent1] > _ufs[parent2]) //让parent1标记大集合根结点，parent2标记小集合根结点
			swap(parent1, parent2);
		//将小集合合并到大集合上
		_ufs[parent1]  = _ufs[parent2]; //将小集合根结点的值累加到大集合的根结点上
		_ufs[parent2] = parent1; //将小集合根结点的值改为大集合根结点的编号
		return true;
	}
	//获取并查集中集合的个数
	int getNum() {
		int count = 0; //统计根结点的个数
		for (const int& val : _ufs) {
			if (val < 0) //元素值为负数则为根结点
				count  ;
		}
		return count; //返回根结点的个数
	}
private:
	vector<int> _ufs; //维护各个结点之间的关系
	unordered_map<T, int> _indexMap; //建立元素与数组下标之间的映射关系
};

这样在使用并查集时就可以传入任意类型的元素了。如下：

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

	return 0;
}

并查集的题目

省份的数量

省份的数量

题目描述：

  有 $n$ 个城市，其中一些彼此相连，另一些没有相连，如果城市 $a$ 与城市 $b$ 直接相连，且城市 $b$ 与城市 $c$ 直接相连，那么城市 $a$ 与城市 $c$ 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。
  给你一个 $n\times n$ 的矩阵，其中 $isConnected[i][j]=1$ 表示第 $i$ 个城市和第 $j$ 个城市直接相连，而 $isConnected[i][j]=0$ 表示二者不直接相连。返回矩阵中省份的数量。

解题步骤：

1. 定义一个长度为 $n$ 的数组充当并查集，并将数组中的元素初始化为-1，表示各个城市各自是一个省份。
2. 根据所给矩阵，对并查集中的各个集合进行合并。
3. 并查集中集合的个数即为省份的数量。

代码如下：

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        //1、初始化并查集
        int n = isConnected.size();
        vector<int> ufs(n, -1);
        auto findRoot = [&ufs](int x)->int {
            int parent = x;
            while (ufs[parent] >= 0) {
                parent = ufs[parent];
            }
            return parent;
        };
        //2、根据所给矩阵合并集合
        for (int i = 0; i < n; i  ) {
            for (int j = 0; j < n; j  ) {
                if (isConnected[i][j] == 1) { //城市相连
                    int parent1 = findRoot(i), parent2 = findRoot(j);
                    if (parent1 != parent2) { //需要合并
                        ufs[parent2] = parent1;
                    }
                }
            }
        }
        //3、统计并查集中集合的个数
        int count = 0;
        for (const int& e : ufs) {
            if (e < 0)
                count  ;
        }
        return count;
    }
};

说明一下：

• 在使用并查集解题时不需要实现一个完整的并查集，根据题目要求实现需要用到的逻辑即可。

等式方程的可满足性

等式方程的可满足性

题目描述：

  给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 $equations[i]$ 的长度为4，并采用两种不同的形式之一：“$a$==$b$” 或 “$a$!=$b$”。在这里 $a$ 和 $b$ 是小写字母（不一定不同），表示单字母变量名。
  只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 $true$ ，否则返回 $false$ 。

解题步骤：

1. 定义一个长度为26（变量为小写字母）的数组充当并查集，并将数组中的元素初始化为-1，表示各个字母只有自己等于自己。
2. 根据字符串方程组中的等式，对并查集中的各个集合进行合并（每个集合中的元素都是相等的）。
3. 根据并查集，对字符串方程组中的不等式进行验证，如果两个不相等的变量出现在同一个集合中，则返回 $false$ 。

代码如下：

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        //1、初始化并查集
        vector<int> ufs(26, -1);
        auto findRoot = [&ufs](int x)->int {
            int parent = x;
            while (ufs[parent] >= 0) {
                parent = ufs[parent];
            }
            return parent;
        };
        //2、根据字符串方程组中的等式合并集合
        for (const string& s : equations) {
            if (s[1] == '=') { //等式
                int parent1 = findRoot(s[0] - 'a'), parent2 = findRoot(s[3] - 'a');
                if (parent1 != parent2) { //需要合并
                    ufs[parent2] = parent1;
                }
            }
        }
        //3、根据并查集验证字符串方程组中的不等式
        for (const string& s : equations) {
            if (s[1] == '!') { //不等式
                int parent1 = findRoot(s[0] - 'a'), parent2 = findRoot(s[3] - 'a');
                if (parent1 == parent2) { //在同一个集合
                    return false;
                }
            }
        }
        return true;
    }
};

这篇好文章是转载于：学新通技术网