【数据结构】并查集-????并查集的优化????

并查集的优化方式就是路径压缩和将节点少的集合向节点多的集合合并。当层数过多时，会影响查找的效率。那如何进行路径压缩呢？路径压缩可以在查找根的过程中进行，路径压缩就是修改当前下标的父节点的下标。为什么要将节点少的集合向节点多的集合合并呢？因为这样可以让更少的节点的层数变高，提高查找效率。

#pragma once
#include <map>
#include <vector>
#include <iostream>
#include <string>
using namespace std;

class UnionFindSet
{
public:
	// 初始状态
	UnionFindSet(size_t n)
		: _ufs(n, -1)
	{}

	// 将x1和x2所在的集合合并
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		// x1和x2已经在同一个集合了
		if (root1 == root2)
			return;

		// x1和x2不在同一个集合,需要合并两个集合
		// 默认root1是节点多的集合
		// 将节点少的集合合并到节点多的集合中
		if (abs(_ufs[root1]) < abs(_ufs[root2]))
			swap(root1, root2);

		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	// 判断x1和x2是否在同一个集合中
	bool Inset(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	// 集合(树)的个数 = 负数的个数
	size_t SetSize()
	{
		size_t size = 0;
		for (size_t i = 0; i < _ufs.size(); ++i)
		{
			if (_ufs[i] < 0)
				++size;
		}
		return size;
	}

	// 找出x的根
	int FindRoot(int x)
	{
		int root = x;
		// 值为负数时即为根
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}

		// 压缩路径
		while (_ufs[x] >= 0)
		{
			// 修改该路径中节点的父亲节点下标
			int parent = _ufs[x];
			_ufs[x] = root;
			x = parent;
		}

		return root;
	}

private:
	vector<int> _ufs;
};

void UnionFindSetTest()
{
	UnionFindSet ufs(10);
	ufs.Union(8, 9);
	ufs.Union(7, 8);
	ufs.Union(6, 7);
	ufs.Union(5, 6);
	ufs.Union(4, 5);

	ufs.FindRoot(9);
}