并查集(C++实现)_c++并查集

目录

一、并查集原理

二、并查集应用

2.1 并查集举例

2.2 并查集数组规律

2.3 并查集功能

三、并查集实现

3.1 并查集

3.2 根据名字查找

四、例题

4.1 省份数量

4.2 等式方程的可满足性

---

一、并查集原理

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

• 并查集并查集，就是看你在哪个集合中，并且可以将集合合并的数据结构！

二、并查集应用

2.1 并查集举例

某公司今年招收10人，上海招收4人，成都招收3人，武汉招收3人；这10个人来自不同的学校，每个学生都是一个独立的小团体，现在给这些学生编号:{0，1，2，3，4，5，6，7，9}；给以下数据用来存储该小集合，数组中的数据代表：该小集合中具有成员的个数：

毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：
上海学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。

一趟火车之旅后，每个小分队成员就互相熟悉，成为了一个朋友圈。

从上图可以看出：
编号为6,7,8同学属于0号小分队，该小分队中有4人(包含队长0)；
编号为4和9的同学属于1号小分队，该小分队有3人(包含队长1)；
编号为3和5的同学属于2号小分队，该小分队有3人(包含队长1)。

2.2 并查集数组规律

此时数组中便会出现以下规律：

1. 数组的下标对集合中元素的编号
2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数
3. 数组中如果为非负数，代表该元素双亲在数组中的下标

在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般地走到了一起，两个小圈子的同学相互介绍，最后成为了一个圈子：

现在0集合有7个人，2集合有3个人，总共有两个朋友圈。

2.3 并查集功能

通过以上例子已知，并查集一般可解决以下问题：

1. 查找元素属于哪个集合
   沿着数组表示树形关系以上一致找到根(即：树中元素为负数的位置)
2. 查看两个元素是否属于同一个集合
   沿着数组表示的树形关系往上一直找到根，如果根相同表明在同一个集合，否则不在
3. 两个集合归并成一个集合
   将两个集合中的元素合并
   将一个集合名称改为另一个集合的名称
4. 集合的个数
   遍历数组，数组中元素为负数的个数即为集合的个数。

三、并查集实现

3.1 并查集

并查集需要有下面的接口

• 查找元素属于哪个集合
• 查看两个元素是否属于一个集合
• 合并两个集合
• 集合的个数

---

查找元素属于哪个集合

---

查看两个元素是否属于一个集合

---

合并集合

我们只能做到将一个集合合并到另一个集合，让其作为子集。

步骤(右集合合并至左集合)：

1. 找到两个集合的根

2. 判断两个集合的根是否不同，相同则不做处理

3. 将右集合中记录集合数累加到左集合中。

4. 再将右集合指向左集合。

---

集合的个数

3.2 路径优化(压缩)

当我们合并集合的时候，如果将大集合合并到小集合中，则会导致路径过长，效率变低。

例我们现在有一个大集合、一个小集合

 然后我们使用两种方式进行合并(一种是小集合并到大集合中，一中是大集合并到小集合中)

很明显，将小集合并到大集合中更能提高性能。

那体现再程序中就是当我们找到根的时候，来判断一下两个集合哪个大即可，然后进行合并：

//合并集合
void Union(int x1, int x2)
{
	//1.找到两个集合的根
	int root1 = FindRoot(x1);
	int root2 = FindRoot(x2);
	//如果两个根不相同---则合并
	if (root1 != root2)
	{
		//默认root1为大集合，判断root2是否大于root1
		if (abs(_ufs[root1]) < abs(_ufs[root2]))
			swap(root1, root2);
		//将小的集合合并到大集合中
		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}
}

当合并出现极端情况时，此时查询根节点就会接近于线性，此时我们要在find中，顺带进行路径压缩。

例：

 此时我们希望路径能压缩至这种形式： 

 

因为我们在findRoot中找到了根，所以我们直接再次将走过的路径让其指向根即可，实现如下：

int FindRoot(int x)
{
	int root = x;
	//因为根为负数，找到负数即可
	while (_ufs[root] >= 0)
	{
		root = _ufs[root];
	}
	//路径压缩
	while (_ufs[x] >= 0)
	{
		//记录父亲节点
		int parent = _ufs[x];
		//让该节点直接指向root
		_ufs[x] = root;
		x = parent;
	}
	return root;
}

3.3 根据名字查找

这里我们可以实现一个根据名字查找编号。

实现思路：

        用一个数组来存放所有学生的信息，再使用map来建立映射关系。

map的使用<string, int>类型，根据名字查找到数组中该学生的下标，使用该下标再访问数组即可查到数据。

//学生信息数组
vector<student_info> arr{ student_info("Brant", 20, 10),
    student_info("James", 40, 70),
 student_info("Curry", 30, 100) };
 
 
//并查集
vector<student_info> UnionFind_arr(3);
map<string, int> UnionFind_map;
 
for (int i = 0; i < arr.size(); i++)
{
    UnionFind_arr[i] = arr[i];
    UnionFind_map[arr[i]._name] = i;
}
 
 
//可以通过名字找到编号
cout << "James信息的下标为:" << UnionFind_map["James"] << endl;
cout << UnionFind_arr[UnionFind_map["James"]] << endl;

 student_info类

class student_info
{
public:
        friend ostream& operator<<(std::ostream& os, const student_info& info);
        student_info(string name,int age,int score)
                :_name(name),_age(age),_score(score)
        {
        }
        string _name;
        int _age;
        int _score;
};
 
ostream& operator<<(std::ostream& os, const student_info& info)
{
        os << "Name: " << info._name << "\n"
                << "Age: " << info._age << "\n"
                << "Score: " << info._score << "\n";
        return os;
}

四、例题

我觉得，把这两道并查集的题目解决，才算学会了并查集。

4.1 省份数量

4.1 省份数量

解题思路：

        这个省份数量就类似我们本篇博客举的实习例子很像，是同一个集合，就将其合并到一起。最后通过统计有几个这样的集合即可。

只不过这题使用了二维数组来表达这种关系。

直接将我们编写的并查集类放入代码中，调用其中的函数即可通过。

 
class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n,-1)
	{}
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		if (root1 != root2)
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}
	}
	int FindRoot(int x)
	{
		int root = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}
		return root;
	}
	bool IsInset(int x1,int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}
	size_t setSize()
	{
        size_t size=0;
        for(int i =0;i<_ufs.size();i++)
        {
            if (_ufs[i]<0)
                ++size;
        }
        return size;
    }
private:
	vector<int> _ufs;
};
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFindSet ufs(isConnected.size());
        for(size_t i = 0;i<isConnected.size();i++)
            for(size_t j = 0;j<isConnected[i].size();j++)
                if (isConnected[i][j] == 1)
                    ufs.Union(i,j);
 
        return ufs.setSize();
    }
};

直接使用并查集思想一样可以写出来

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        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);
                int root2 =findRoot(j);
								if (root1!=root2)
								{
										ufs[root1] += ufs[root2];
										ufs[root2] = root1; 
								}
							}
               
            }
        }
			  size_t size=0;
        for(int i =0;i<ufs.size();i++)
        {
            if (ufs[i]<0)
                ++size;
        }
        return size;
				
    }
};

4.2 等式方程的可满足性

等式方程的可满足性

这一题我们首先处理相等

遍历数组，如果是相等，我们就将其归到同一个集合中，则表示该等式中的变量都是相等的。

然后我们再遍历数组中的不相等方程，找到两个变量的根，因为是不相等，则这两个变量肯定不在一个集合中，通过 find 如果发现两个变量是同一个根，则表示在同一个集合中，即方程不正确。

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        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');
                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;
    }
};