并查集与搜索的联系
在 LeetCode 上练习时了解到,并查集 这一数据结构比较常用于解决图论方面的问题,其应用场景与搜索有很多重叠。例如,两者都可用于求无向图中连通分量 (connected component or just component)的个数。下图1中就有三个连通分量,分别以不同颜色标出:
LeetCode 例题:547. 省份数量 并查集 鉴于 STL 没有实现并查集(已知 Boost 有),我们需要自己动手实现:以 vector<int> 为本体,辅以 get_root() 和 merge_set() 两个函数,即可完成。注意,此实现舍弃了性能的完整性2,追求的目标是代码量小、功能够用,适用于做题和笔试场景。
值得注意的 …