数据结构--并查集

原理

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。此后我们可能要反复用到查询某一个元素归属于那个集合的运算，适合于描述这类问题的抽象数据类型称为并查集。

并查集的本质就是一个森林，属于同一个集合的元素在同一颗树中，我们可以采用一个数组来描述这个森林：数组下标对应元素的编号，该下标对应的数组值表示该元素的父亲节点的下标，如果为负值-1，表示当前元素是根节点。

开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并，为了查询效率，应该在合并时让数据量小的集合向数据量大的集合合并（这样就是让数据量小的树的元素高度增加，而数据量大的树的元素的高度不变），同时为了避免某棵树的高度过高，我们还需要进行路径压缩，可以选择在查询某个元素时直接将该元素连接到根节点下面，这样下次查询时速度就很快了。

我们这里实现时数组的下标对应的是元素的编号，而我们原本的数据类型是不确定的，因此我们需要将原来的数据类型映射到数组下标上：只需要将数据插入到一个数组当中，这样原始数据就具有了下标，同时我们还可以通过下标直接找到原始数据；为了还可以通过原始数据找到下标，我们可以通过关联式容器map建立原始数据到其下标的映射。

实现

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

using namespace std;

template<class T>
class unionFindSet {
public:
	unionFindSet(vector<T>& datas)
		:_elements(datas)
		,_union(datas.size(),-1)
	{
		int i = 0;
		for (; i < _elements.size(); ++i) {
			_index.insert(make_pair(_elements[i], i));
		}
	}

	~unionFindSet()
	{}

	//检查2个元素是否在同一个集合当中
	bool IsInOneSet(T data1, T data2) {
		int root1 = FindRoot(data1);
		int root2 = FindRoot(data2);
		if (-1 == root1 || -1 == root2) {
			return false;
		}

		return root1 == root2;
	}

	//合并2个集合
	bool Union(T data1, T data2) {
		int root1 = FindRoot(data1);
		int root2 = FindRoot(data2);
		if (-1 == root1 || -1 == root2) {
			return false;
		}

		_union[root1] = root2;
		return true;
	}

	//查找集合的个数
	int Count() {
		int ans = 0;
		for (auto e : _union) {
			if (-1 == e) {
				++ans;
			}
		}

		return ans;
	}
private:
	//返回元素data的根节点
	int FindRoot(T& data) {
		if (_index.end() == _index.find(data)) {
			return -1;
		}
		int pos = _index[data];
		while (-1 != _union[pos]){
			pos = _union[pos];
		}

		if (pos != _index[data]) {
			//将该元素连接到根节点下面
			_union[_index[data]] = pos;
		}
		return pos;
	}


private:
	vector<int> _union;				//集合
	vector<T> _elements;			//将原始数据和下标建立关系的数组
	map<T, int> _index;	//利用原始数据寻找它在_elemrnts中的下标的关联式容器
};

int main() {
	vector<string> elements = { "alice","bob","jone","jason","tom","jerry","willon","michael" };
	unionFindSet<string> s(elements);
	printf("count: %d\n", s.Count());
	printf("is %s and %s in one set:%d\n", "alice", "bob", s.IsInOneSet("alice", "bob"));
	s.Union("alice", "bob");
	printf("is %s and %s in one set:%d\n", "alice", "bob", s.IsInOneSet("alice", "bob"));
	printf("count: %d\n", s.Count());
	printf("is %s and %s in one set:%d\n", "alice", "tom", s.IsInOneSet("alice", "tom"));
	s.Union("alice", "tom");
	printf("is %s and %s in one set:%d\n", "tom", "bob", s.IsInOneSet("tom", "bob"));
	printf("count: %d\n", s.Count());
	return 0;
}