文章和资源同步更新至微信公众号：算法工程师之路
今天我们要介绍一种简单但对于合并和查找都十分高效的结构——并查集，其底层实现也十分简单，并且应用非常广泛，比如最小生成树算法中的Kruskal算法，里面有使用了并查集的结构！并且在并查集结构为了加速查找，底层使用基于hash的容器，在CPP中，叫做unordered_map! unordered_map是C++11标准的东西，其为基础类型提供了hash模板，但是如果自定义类型呢？我们如何去构建这个容器？下面会给你答案！
在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){ ... }接下来我们看一个自定义类型使用unordered_map的例子，而另外一个unordered_set的重写方式是一样的，大家自己可以去试一试！在这里我们使用自定义类型为Key，然后分别使用sturct建立仿函数，重写hash函数和equal_to函数！！！然后就可以愉快的使用啦！
#include <unordered_map> #include <string> #include <iostream> using namespace std; struct Key{ string first; string second; Key(string first, string second){ this->first = first; this->second = second; } }; struct KeyHash{ size_t operator()(const Key& k) const{ return hash<string>()(k.first) ^ (hash<string>()(k.second) << 1); } }; struct KeyEqual{ 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 = { {{"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，由于是一个递归的过程，在找到代表节点后，将所有遍历过的节点的父节点都设置为代表节点，因此就将链表压平了！等下次查找时候就会快很多，不用再遍历那么多的节点了！ 由于上述的操作都是建立在hash函数的组织之下，因此效率非常高，速度也非常快！并且代码量也不多，主要就是查找函数中的递归算法，一定要理解清楚！
#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}); size.insert({var, 1}); } } char findRep(char node){ char f = father[node]; if (f != node){ f = findRep(f); } father[node] = 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; }基于并查集的算法，最经典的就是最小生成树算法——Kruskal算法，我们下次再说，如果你想要提前了解，笔者已经将程序放到公众号资源中了！欢迎关注，回复关键字即可获取！ 以上完整代码文件（C++版）,文件名为：并查集示例.cpp，请关注我的个人公众号 （算法工程师之路），回复"左神算法基础CPP"即可获得，并实时更新！希望大家多多支持哦~
公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)
