高阶数据结构——并查集

1. 并查集的介绍

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。

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

比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体，我们给这10个人进行编号。

每个地方的学生自发组织成小分队一起上路，于是：西安的4名同学（编号为0，6，7，8）组成了一个团体，成都的三名同学（编号为1，4，9）组成了一个团体，武汉的3名同学（编号为2，3，5）组成了一个团体。假设由编号最小的同学担任队长。

有了这个结构之后，我们很容易就能判断出来某两位同学是否属于同一个团体，并且合并两个集合也非常方便，这就是并查集的价值所在。

2. 并查集的原理

在实际中我们可以通过一个数组来实现并查集，还是上面那个例子。我们定义一个数组，这个数组的下标就是每个成员的编号，数组中的值有两层意思：

1.对队长（根节点）来说，数组中保存这个集合中所有元素的个数 * -1。

2.对成员（除了根节点的其他结点）来说，数组中保存的是他的父节点的下标。

所以数组中值 < 0 的都是根节点，根节点得绝对值是这个集合的元素个数。

最初一开始所有同学都是一个独立的团体，所以先初始化为 -1。

后续相同城市的同学组成了一个团体。

物理结构图如下：

逻辑结构图如下：

并查集可以用来解决哪些问题？

1.查找元素属于哪个集合

由于数组中保存的是他父节点的下标，所以我们可以根据这个特点，一路向上查找，直到找到一个是值为负数的结点即可

2.查找两个元素是否属于同一集合

沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在

3.将两个集合合并成一个集合

需要做以下两步

• 将两个集合中的元素合并
• 将一个集合名称改成另一个集合的名称

比如上面的例子，{0，6，7，8}集合和{1，4，9}进行合并。

注意观察数组的变化，1号由原来的-3变成0，0号由原来的-4变成了-7。

4.集合的个数

遍历数组，数组中元素为负数的个数即为集合的个数。

3. 并查集的实现

并查集的实现通常包含如下接口：

• 1.查找父节点下标
• 2.合并两个集合
• 3.返回集合的个数
• 4.判断两个值是否在同一个集合中

class UnionFindSet { public: 	UnionFindSet(size_t n) 		: _ufs(n, -1) 	{}  	//返回父节点的下标 	size_t FindRoot(size_t posi);     //合并两个集合 	bool Union(size_t x1, size_t x2);     //返回集合的个数 	size_t Count();     //判断两个值是否在同一个集合中     bool InSameSet(size_t x1, size_t x2);   private: 	vector<int> _ufs; };

并查集的特点：

1.数组的下标对应集合中元素的编号

2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数

3. 数组中如果为非负数，代表该元素双亲在数组中的下标

3.1 找到根节点

size_t FindRoot(size_t posi) { 	while (_ufs[posi] >= 0) 	{ 		posi = _ufs[posi]; 	}  	return posi; }

查找思路：如果一个结点是根节点，那么直接返回下标即可，如果不是根节点，那么就一路向上查找，直到找到根。

以上图为例，比如我们要查找9的根。根据数组我们可以看到9的父节点是1。继续向上查找，1号的父节点是0，到了0号，我们发现数据中保存的是-7，一个小于0的数，表示这个结点就是一个父节点。所以我们最终得到了9的根节点是0号。

3.2 合并两个集合

bool Union(size_t x1, size_t x2) { 	int root1 = FindRoot(x1); 	int root2 = FindRoot(x2);  	// 如果他们本身就在同一个集合中 	if (root1 == root2) 		return false;  	// 默认将root1为较大的集合 	if (_ufs[root1] > _ufs[root2]) 		swap(root1, root2);  	//将root2合并到root1下 	_ufs[root1] += _ufs[root2]; 	_ufs[root2] = root1;  	return true; }

先找到两个集合的根，如果这两个不在一个集合我们就进行合并，合并的方式是将一个集合当作另一个集合的根。

当然，上面的只是逻辑图，物理模型如下：

还有一点值得注意，就是我们要让root1为较大的那个集合，root2为较小的那个集合，这样做可以提高一点效率，因为我们是将root2合并到root1上的，如果root2的元素过多，root2再接到root1下，那么将会导致，root2中的所有元素每次都要多找一个值才能找到。

3.3 集合的个数

size_t Count() { 	size_t count = 0; 	for (auto e : _ufs) 	{ 		if (e < 0) 			++count; 	} 	return count; }

遇到一个小于0的数说明这是一个集合，每遇到一个集合直接++，最后返回最终的结果。

3.4 判断两个数是否在同一个集合

bool InSameSet(size_t x1, size_t x2) { 	int root1 = FindRoot(x1); 	int root2 = FindRoot(x2);  	if (root1 == root2) 		return true; 	else 		return false; }

直接找根即可，如果是同一个根就说明在同一个集合。

3.5 路径压缩

并查集的优势就是，能快速的查看两个数是否属于同一集合。但是有个问题，我们的合并两个集合是将一个集合直接变成另一个集合的孩子。也就是说，如果数据量较大的情况下，会导致并查集的高度变得很大，也就影响了查找效率，所以我们可以使用路径压缩的方式，减少树的高度。

路径压缩的方式是：我们使用FindRoot查找一个结点时，就把这个结点到根节点路径上的所有结点都变成根的孩子结点。

以下图为例：我们使用FIndRoot查找9号结点的根。

将9到根结点0路径上所有的结点都变成根节点0的孩子，也就是将9和1变成0的孩子。

我们发现以后再查找9所在的集合，只需找两次就行了。

//返回父节点的下标 size_t FindRoot(size_t posi) { 	int root = posi; 	while (_ufs[root] >= 0) 	{ 		root = _ufs[root]; 	}  	//路径压缩 	while (_ufs[posi] >= 0) 	{ 		int parent = _ufs[posi]; 		_ufs[posi] = root; 		posi = parent; 	}  	return posi; }

3.6 完整代码

class UnionFindSet { public: 	UnionFindSet(size_t n) 		: _ufs(n, -1) 	{}  	//返回父节点的下标 	size_t FindRoot(size_t posi) 	{ 		int root = posi; 		while (_ufs[root] >= 0) 		{ 			root = _ufs[root]; 		}  		//路径压缩 		while (_ufs[posi] >= 0) 		{ 			int parent = _ufs[posi]; 			_ufs[posi] = root; 			posi = parent; 		}  		return posi; 	}  	bool Union(size_t x1, size_t x2) 	{ 		int root1 = FindRoot(x1); 		int root2 = FindRoot(x2);  		// 如果他们本身就在同一个集合中 		if (root1 == root2) 			return false;  		// 默认将root1为较大的集合 		if (_ufs[root1] > _ufs[root2]) 			swap(root1, root2);  		//将root2合并到root1下 		_ufs[root1] += _ufs[root2]; 		_ufs[root2] = root1;  		return true; 	}  	size_t Count() 	{ 		size_t count = 0; 		for (auto e : _ufs) 		{ 			if (e < 0) 				++count; 		} 		return count; 	}  	bool InSameSet(size_t x1, size_t x2) 	{ 		int root1 = FindRoot(x1); 		int root2 = FindRoot(x2);  		if (root1 == root2) 			return true; 		else 			return false; 	}  private: 	vector<int> _ufs; };

4. 并查集相关题目

4.1 省份数量

题目链接：LCR 116. 省份数量 - 力扣（LeetCode）

题目描述：

解题思路：如果两个城市连接了，就将他们加入同一个集合，最终判断有几个集合即可。

方法一：使用我们自己写的并查集

class UnionFindSet { public: 	UnionFindSet(size_t n) 		: _ufs(n, -1) 	{}  	//返回父节点的下标 	size_t FindRoot(size_t posi) 	{ 		int root = posi; 		while (_ufs[root] >= 0) 		{ 			root = _ufs[root]; 		}  		//路径压缩 		while (_ufs[posi] >= 0) 		{ 			int parent = _ufs[posi]; 			_ufs[posi] = root; 			posi = parent; 		}  		return posi; 	}  	bool Union(size_t x1, size_t x2) 	{ 		int root1 = FindRoot(x1); 		int root2 = FindRoot(x2);  		// 如果他们本身就在同一个集合中 		if (root1 == root2) 			return false;  		//将root2合并到root1下 		_ufs[root1] += _ufs[root2]; 		_ufs[root2] = root1;  		return true; 	}  	size_t Count() 	{ 		size_t count = 0; 		for (auto e : _ufs) 		{ 			if (e < 0) 				++count; 		} 		return count; 	}  	bool InSameSet(size_t x1, size_t x2) 	{ 		int root1 = FindRoot(x1); 		int root2 = FindRoot(x2);  		if (root1 == root2) 			return true; 		else 			return false; 	}      void Print()     {         for (auto e : _ufs)         {             std::cout << e << " ";         }         std::cout << std::endl;     }  private: 	vector<int> _ufs; };   class Solution { public:     int findCircleNum(vector<vector<int>>& isConnected) {         int n = isConnected.size();         UnionFindSet ufs(n);          for (size_t i = 0; i < n; i++)         {             for (size_t j = 0; j < n; j++)             {                 if (isConnected[i][j] == 1)                 {                     ufs.Union(i, j);                 }             }         }        ufs.Print();          return ufs.Count();     } };

发现相同省份就将他们加入同一个集合即可。

但是这种方式非常麻烦，要先手动实现一个并查集，实际上我们可以发现，我们只用到了Union函数和Count函数。

方案二：模拟并查集

我们完全可以用数组模拟出一个并查集，只需要实现其中的合并功能就行了。

class Solution { public:     int findCircleNum(vector<vector<int>>& isConnected) {         int n = isConnected.size();         vector<int> ufs(n, -1);          auto FindRoot = [&ufs](size_t index)         {             int root = index;             while (ufs[root] >= 0)             {                 root = ufs[root];             }             return root;         };          for (size_t i = 0; i  < n; i++)         {             for (size_t j = 0; j < n; j++)             {                 if (isConnected[i][j] == 1)                 {                     //先找根                     int root1 = FindRoot(i);                     int root2 = FindRoot(j);                      if (root1 != root2)                     {                         ufs[root1] += ufs[root2];                         ufs[root2] = root1;                     }                 }             }         }          size_t count = 0;         for (auto e : ufs)         {             if (e < 0)                 ++count;         }                  return count;     } };

4.2 等式方程的可满足性

题目链接：990. 等式方程的可满足性 - 力扣（LeetCode）

题目描述：

解题思路：如果表达式的符号为==，就将左右两个操作数加入同一个集合中，遍历一遍之后，再次遍历，找到表达式为 != 的符号，判断左右两边是否在同一个集合中，如果不满足条件则返回false，满足则返回true。

class Solution { public:     bool equationsPossible(vector<string>& equations) {         int n = equations.size();         vector<int> ufs(26, -1);          auto FindRoot = [&ufs](size_t index)         {             while (ufs[index] >= 0)             {                 index = ufs[index];             }             return index;         };          for (auto& str : equations)         {             if (str[1] == '=')             {                 int root1 = FindRoot(str[0] - 'a');                 int root2 = FindRoot(str[3] - 'a');                  if (root1 != root2)                 {                     ufs[root2] = root1;                 }             }         }          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;     } };