本篇主要是介绍并查集的内容：所谓并查集就是一种描述不相交集合的数据结构，即若一个问题涉及多个元素，它们可以划分到不同集合，同属一个集合内的元素等价，不同集合内的元素不等价。

文章目录

• 一、并查集原理
• 二、并查集实现
• 三、并查集应用

一、并查集原理

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

如下图所示：

 结论：1、数组下标对应集合中元素的编号。

            2、数组中如果为负数，负数代表根，数字代表该集合中元素的个数。

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

如果其中两棵树变成棵树的情况，如下图所示：

 通过上面的两张图片可以知道：并查集一般可以解决：

1、查找元素属于哪个集合（沿着数组表示树形关系以上一直找到根（即树中元素为负数的位置）。

2、查看两个元素是否属于同一个集合（沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在）。

3、将两个集合归并成一个集合（将两个集合中的元素合并，将一个集合名称改成另一个集合的名称） 。

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

二、并查集实现

#include
#includeusing namespace std;class UnionFindSet
{
public://初始化：将数组中元素全部设置为1UnionFindSet(int size):_ufs(size, -1){}//给数组元素一个编号，找到该元素所在集合的名称size_t FindRoot(int x){while (_ufs[x] >= 0)x = _ufs[x];return x;}//合并两个集合void Union(int x1, int x2){int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (root1 != root2){_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}}//找出并查集中根的个数size_t SetCount(){size_t count = 0;for (int i = 0; i < _ufs.size(); i++)if (_ufs[i] < 0)count++;return count;}
private:vector _ufs;
};
int main()
{UnionFindSet ufs(10);ufs.Union(0, 6);ufs.Union(0, 7);ufs.Union(0, 8);ufs.Union(1, 4);ufs.Union(1, 9);ufs.Union(2, 3);ufs.Union(2, 5);cout << ufs.SetCount() << endl;
}

三、并查集应用

        1.省份的数量OJ链接

/*class UnionFindSet
{
public:UnionFindSet(size_t n):_ufs(n,-1){}size_t FindRoot(int x){while(_ufs[x]>=0)x=_ufs[x];return x;}void Union(int x1,int x2){int root1=FindRoot(x1);int root2=FindRoot(x2);if(root1!=root2){_ufs[root1]+=_ufs[root2];_ufs[root2]=root1;}}size_t SetCount(){size_t count=0;for(int i=0;i<_ufs.size();i++)if(_ufs[i]<0)count++;return count;}
private:vector _ufs;
};
class Solution {
public:int findCircleNum(vector>& isConnected) {//手动创建一个并查集UnionFindSet ufs(isConnected.size());//如果此时isConnected[i][j]==1说明第i个和第j个城市直接相连，可以认为二者是在同一棵树中for(int i=0;i&_ufs,int x){while(_ufs[x]>=0)x=_ufs[x];return x;}int findCircleNum(vector>& isConnected) {vector _ufs(isConnected.size(), -1);for(int i=0;i

class Solution {
public:size_t FindRoot(vector&ufs,int x){while(ufs[x]>=0)x=ufs[x];return x;}bool equationsPossible(vector& equations) {vector _ufs(26,-1);//第一遍是将所有的变量之间相等的放入同一个集合中for(auto&str:equations){if(str[1]=='='){int root1=FindRoot(_ufs,str[0]-'a');int root2=FindRoot(_ufs,str[3]-'a');if(root1!=root2){_ufs[root2]+=_ufs[root1];_ufs[root1]=root2;}}}//第二遍是讲不等的变量如果出现在同一个集合中则直接返回falsefor(auto&str:equations){if(str[1]=='!'){int root1=FindRoot(_ufs,str[0]-'a');int root2=FindRoot(_ufs,str[3]-'a');if(root1==root2)return false;}}return true;}
};