原理

在一些应用问题中，需要将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;
}