1. 并查集数据结构

• 并查集：

  在一些应用场景之下，我们需要将$N$个元素，分为不同的集合，这些集合不相交，然后按照某种规律（用户自己决定），将归于同一组的元素进行合并。在这个过程中，会反复使用查询某两个元素是否在同一个集合中的算法。
  用来描述这类的抽象问题的数据结构就是：并查集。

  • 例：

    例如一个交际圈，我和我的朋友小c两个人组成了一个交际圈（以我为中心），小c的朋友和我的朋友小c组成一个交际圈（以小c朋友为中心）。在小c介绍我们两个的时候，我们就可以组成一个更大的朋友圈了。

• 存储结构：

  • 逻辑结构：

    如下图，我们可以一颗多叉树来描述一个集合。
    
    我们判断两个元素是否在同一个集合中，就查找这个两个元素的根节点是否都是同一个元素。
    所以，这注定了：并查集的逻辑存储结构一定是一个森林。
    

  • 物理结构：

    首先我们不可能像二叉树一样来描述一颗多叉树（因为我们一共需要多少个分支）。这里就提供高效常用方案：

    1. 双亲表示法（指父亲）

       因为我们并查集的特点：判断是否在同一个集合中，只需要判断根节点是否是同一个节点，所以我们可以利用vector<int>进行数据的映射。

    方案：

    • 下标代表元素编号，内容代表该编号元素的父亲的编号。

  如图：

  
  例如：元素编号为6、7、8的元素的父亲节点是元素编号为0的元素，那么对应存储结构中的，v[6]v[7]v[8]中的值就是编号0。

1.1 顺序存储的规定

• 我们需要对顺序结构做如下规定：

1. 数组的下标对应的集合中元素的编号。
2. 数组中如果有负数，符号代表该编号元素为根，该数字代表该集合下有多少个元素。
3. 数组中如果为非负数，代表该元素双亲在数组中的下标（/编号）。

1.2 元素和编号的映射

• 该存储方法有一个缺陷，我们的数据需要先进行编号。所以，我们可以利用vector和map优先进行元素和编号的映射：

template<class T>
class mapping
{
public:
	mapping(const T* a, size_t size)
	{
		_v.reserve(size);
		for (size_t i = 0; i < size; ++i)
		{
			_v.push_back(a[i]);
			_m[a[i]] = i;
		}
	}
	std::vector<T> _v;		//编号找人
	std::map<T, int> _m;		//人找编号
};

2. 并查集操作

• 一般而言，并查集会提供如下操作：

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

     我们只需要延该路径，找到负数就找到根，就找到属于哪一个集合了。

  2. 查看两个元素是否是同一个集合

     查看两个元素的根是否相同。

  3. 将两个元素合并为一个集合

     将根合并即可。将其中一个元素的根，合并到另外一个根上即可。

  4. 集合的个数

     遍历数组，看数组中有多少内容为负数。

2.1 模拟

class unionfindset
{
public:
	unionfindset(size_t n)
		: _ufs(n, -1)
	{
	}
	//1、找根
	int findroot(int x)
	{
		int parent = x;
		while (_ufs[parent] >= 0)
		{
			parent = _ufs[parent];
		}
		return parent;
	}
	//2、合并
	bool unionset(int x, int y)
	{
		//先找根
		int root1 = findroot(x);
		int root2 = findroot(y);
		if (root1 == root2)
		{
			return false;
		}
		else
		{
			//没有规定小的链大的，还是大的链小的
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
			return true;
		}
	}

	//3、判断是否在同一个集合
	bool inset(int x, int y)
	{
		return findroot(x) == findroot(y);
	}

	//4、返回集合个数
	size_t size()
	{
		size_t count = 0;
		for (auto e : _ufs)
		{
			if (e < 0)
			{
				++count;
			}
		}
		return count;
	}
	
private:
	std::vector<int> _ufs;
};

3. 并查集优化 – 路径压缩

按照我们上面的处理，会有一个致命的问题：

• 如果我们的数据量足够大，那么可能某棵多叉树的高度会越来越深（和合并的逻辑有关系）。

  

• 如图，此时如果我们想要查找e7的元素的根，几乎就是一个$O(N)$的时间复杂度。所以为了避免这种情况发生，我们通常会进行路径压缩：

  • 路径压缩我们可发生在找根的时候：找到某个元素的根的时候，我们就可以把路径上所有元素的父亲编号都改为根编号。

  • 如图：

  

int findroot(int x)
{
	int parent = x;
	while (_ufs[parent] >= 0)
	{
		parent = _ufs[parent];
	}
	//找到根了parent
	int cur = x;
	while (_ufs[cur] >= 0) //当遇到根节点的字节点就停止
	{
		int next = _ufs[cur]; //保存父节点
		_ufs[cur] = parent; //更新根节点
		cur = next;
	}
	return parent;
}

完整代码

#pragma once

#pragma once
#include<iostream>
#include<vector>
#include<map>
#include<string>

template<class T>
class mapping
{
public:
	mapping(const T* a, size_t size)
	{
		_v.reserve(size);
		for (size_t i = 0; i < size; ++i)
		{
			_v.push_back(a[i]);
			_m[a[i]] = i;
		}
	}
	std::vector<T> _v;		//编号找人
	std::map<T, int> _m;		//人找编号
};


class unionfindset
{
public:
	unionfindset(size_t n)
		: _ufs(n, -1)
	{
	}
	//1、找根
	int findroot(int x)
	{
		int parent = x;
		while (_ufs[parent] >= 0)
		{
			parent = _ufs[parent];
		}
		//找到根了parent
		int cur = x;
		while (_ufs[cur] >= 0) //当遇到根节点的字节点就停止
		{
			int next = _ufs[cur]; //保存父节点
			_ufs[cur] = parent; //更新根节点
			cur = next;
		}
		return parent;
	}
	//2、合并
	bool unionset(int x, int y)
	{
		//先找根
		int root1 = findroot(x);
		int root2 = findroot(y);
		if (root1 == root2)
		{
			return false;
		}
		else
		{
			//没有规定小的链大的，还是大的链小的
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
			return true;
		}
	}

	//3、判断是否在同一个集合
	bool inset(int x, int y)
	{
		return findroot(x) == findroot(y);
	}

	//4、返回集合个数
	size_t size()
	{
		size_t count = 0;
		for (auto e : _ufs)
		{
			if (e < 0)
			{
				++count;
			}
		}
		return count;
	}


private:
	std::vector<int> _ufs;
};

完。希望这篇文章能够帮助你！！！