高阶数据结构之并查

并查集的概念

之前我们曾学过树，二叉树、二叉搜索树、红黑树、AVL树等，而并查集可以看做是这些树的集合，也就是森林，它也是一种树型结构，不过是顺序的树型结构，如果有学过堆的同学应该会很熟悉。

它的作用是判断集合是否相交，并且将有关系的集合进行合并，并且可以查询这些集合，这就是为什么它被称作并查集。

概念：并查集是一种树型结构，从结构上看和堆十分类似

作用：它可以用来判断集合是否相交、合并相关集合、并且提供查询操作

并查集的具体实现

假设有个公司秋招，它招了10个人，其中有4个湖南的（0,3,5,8），3个广东的（1,4,6），3个广西的（2,7,9），最初这十个人互不相识，我们可以看做10个人互相之间没有关系，因此可以这样建表。

由于十个人互相之间没有关系，可以看做每个个体自己就单纯代表自己。

然后他们到达公司后，公司的经理以地域划分，并且分别选拔了人为队长。

其中湖南的0号为队长，广东的1号为队长，广西的2号为队长，这样这三伙人就分别有了关系，表就变成了这样。

从表中可以看出来，我们能从队员找到队长，这可以看做是一个树型结构。

这就是并查集的表示，而有时候，又会出现合并的情况，依旧拿上面的例子说。

公司有个项目，需要多个组合作，经理让湖南组和广东组一起合作，来完成这个项目，然后让0号员工带队，此时湖南组和广东组应该合并，其合并过程和分组过程类似，最后的数据如下

可以看到，1号员工的组长变成了0，而其下面的组员没变，整体结构变成了这样：

这就是并查集的合并。

那么具体的代码如下：

#include<iostream>
#include<vector>
#include<map>
using namespace std;

class DSU {
public:
	DSU(int n):
		_v(n,-1)
	{
	}
	int findRoot(int x)
	{
		int root = x;
		while (_v[root] >= 0)
		{
			root = _v[root];
		}
		return root;
	}

	void Union(const int& x1, const int& x2)
	{
		int root1 = findRoot(x1);
		int root2 = findRoot(x2);

		if (root1 != root2)
		{
			_v[root1] += _v[root2];
			_v[root2] = root1;
		}
	}

	int GetSize()
	{
		int n = 0;
		for (int i = 0; i < _v.size(); i++)
		{
			if (_v[i] < 0)
			{
				n++;
			}
		}
		return n;
	}

private:
	vector<int> _v;
};

路径压缩

在并查集的使用过程中，可能会在极端情况下出现单边树的情况，或者当数据量过大，树结构有很多层的情况，这会导致并查集的查询效率降低。

比如上面的场景，假设所有人都让上一号人进行管理，那么就会变成一个单边树，查询组长的效率就会降低。

这时就需要路径压缩算法来减少层数，这样就能够提高效率。

我们可以在每次寻找根的时候，可以顺便将路径给压缩，即直接将节点和根连接在一起。

	int findRoot(int x)
	{
		int root = x;
		while (_v[root] >= 0)
		{
			root = _v[root];
		}

        //此时找到了root，也有x
        while(_v[x] >= 0)
        {
            int parent = _v[x];
            _v[x] = root;
            x = parent;
        }

		return root;
	}