今天我们要介绍一种简单但对于合并和查找都十分高效的结构——并查集，其底层实现也十分简单，并且应用非常广泛，比如最小生成树算法中的Kruskal算法，里面有使用了并查集的结构！并且在并查集结构为了加速查找，底层使用基于hash的容器，在CPP中，叫做unordered_map! unordered_map是C++11标准的东西，其为基础类型提供了hash模板，但是如果自定义类型呢？我们如何去构建这个容器？
在STL库中，我们要注意区别map和unordered_map以及set和unordered_set，其中map和set底层数据结构为红黑树，且为关联容器且按照关键字有序的保存元素，而另外两个其底层数据结构为哈希函数所组织的，查找效率为O(1)。
在STL库中，我们要注意区别map和unordered_map以及set和unordered_set，其中map和set底层数据结构为红黑树，且为关联容器且按照关键字有序的保存元素，而另外两个其底层数据结构为哈希函数所组织的，查找效率为O(1)。
由于在STL中，有关于hash的数据结构值针对于基础数据类型如int, string等提供了hash模板，因此如果想要使用自定义类，那么我们需要重写仿函数，也就是自定义hash函数！一般来说，我们需要重写以下两个函数：
注意：重写的两个函数为常函数，一定不要忘了加const
// hash函数 size_t operator()(const Key& k) const{ ... } // 判断键值是否相等 bool operator()(const Key& k1, const Key& k2){ ... } #include <unordered_map> #include <string> #include <iostream> using namespace std; struct Key{ //自定义key string first; string second; Key(string first, string second){ this->first = first; this->second = second; } }; struct KeyHash{ //重载key的hash函数 size_t operator()(const Key& k) const{ return hash<string>()(k.first) ^ (hash<string>()(k.second) << 1); } }; struct KeyEqual{ //重载key的equal函数 bool operator()(const Key& lhs, const Key& rhs) const{ return lhs.first == rhs.first && lhs.second == rhs.second; } }; int main(int argv, char** argc){ unordered_map<Key, string, KeyHash, KeyEqual> m = { //使用自定义key作为健 {{"teddy", "zhang"}, "example"}, {{"mary", "sue"}, "another"} }; Key a("teddy", "zhang"); cout << m[a] << endl; for(auto s: m){ cout << s.second << endl; } }并查集的结构非常简单，但是很有实用性，在大量数据平均情况下，查找的复杂度可以为O(1)，其原理如下： 首先我们将一个序列的每个元素都当做一个集合，同时将这个元素标记为这个集合的代表节点，那么如何标记呢？很简单，其父节点是自己的节点就叫做代表节点！因此，我们在并查集结构中使用hash_map(也就是STL中的unordered_map)来进行信息储存，key表示当前节点，value表示父节点！然后我们还要建立另一个hash_map用来保存集合的大小的信息，key表示节点，value表示当前节点所在集合中的节点总数！
注意：节点总数的信息只对代表节点有效，其他节点这个信息是无效的！并且这个并查集结构对外调用的方法有三个，分别是：
findRep() 查找代表节点
Union() 合并两个集合，合并时小集合会合并到大集合下，总的代表节点为大集合的代表节点
isSameSet() 用来判断两个集合是不是在同一个集合下
合并两个集合： 合并时，集合小的代表节点会直接挂在集合大的代表节点下，从而完成合并！ 查找代表节点： 一定要注意，这是并查集的核心功能，在查找代表节点时，会使用递归的方式，比如下方图中，当查找元素8的代表节点时，会不停的判断当前节点和其父节点是不是同一个节点，如果是，则找到代表节点1，由于是一个递归的过程，在找到代表节点后，将所有遍历过的节点的父节点都设置为代表节点，因此就将链表压平了！等下次查找时候就会快很多，不用再遍历那么多的节点了！
#include <hash_map> #include <iostream> #include <vector> using namespace std; using namespace __gnu_cxx; // linux下使用，window请注释 // 只有每个集合的代表节点是自己指向自己的，这也是并查集的特殊节点唯一标示 class UnionFindSet{ private: hash_map<char, char> father; // value表示父节点 hash_map<char, int> size; public: UnionFindSet(vector<char> data){ father.clear(); size.clear(); for(auto var : data){ father.insert({var, var}); //每个元素的father是它自己，表示每个元素都属一个集合 size.insert({var, 1}); //每个集合个数为1 } } char findRep(char node){ char f = father[node]; if (f != node){ f = findRep(f); } father[node] = f; //设置node的father为f，压平链表 return f; } bool isSameSet(char a, char b){ return findRep(a) == findRep(b); } void Union(char a, char b){ char aRep = findRep(a); char bRep = findRep(b); if(aRep != bRep){ int aSize = size[aRep]; int bSize = size[bRep]; if(aSize > bSize){ father[b] = a; size[a] += size[b]; } else{ father[a] = b; size[b] += size[a]; } } } }; int main(int argc, char** argv){ vector<char> tmp = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}; UnionFindSet s(tmp); s.Union('A', 'B'); cout << s.isSameSet('A', 'B') << endl; }注：本文参考了：并查集详解和STL中的自定义哈希
