并查集

并查集把对象划分为彼此不相交的集合，每个对象属于其中一组。find取得对象所在组的代表，union把两组并成一组；比较两个对象的代表，就可以判断它们目前是否处在同一个分组里。

无向图逐步加入边时，一条边可以要求合并两个端点所属的连通分量。连通关系具有自反、对称与传递性，适合这种分组；有向图中“从A能到B”不一定反向成立，不能直接用同一种合并规则替代有向可达分析。

参考：[1]

一种实现让每个对象记录一个父链接，沿链接到达指向自身的根。合并两组时，先找到两棵树的根，再把一个根连到另一个根；只把任意普通节点改连，而未确认代表，可能破坏预期的分组关系。

按大小合并时，总让较小的树接到较大的树下，控制深度增长。路径压缩则在查找途中把已经过的节点更直接地连向根，减少后续重复查找走过的链接；代表可能随合并变化，不适合作为永久业务身份的名称。

参考：[1]

仅采用按大小合并，树深度就可取得对数上界；路径压缩进一步改善一长串操作中的查找工作，但具体成本结论仍要与采用的合并和压缩规则对应。不能把某一次查找很快，直接说成所有实现每次都只做固定工作。

基础并查集适合不断合并，不能在删除一条图边后自动判断原分量是否应拆开。它也不保存两点之间的完整路径。需要删边、恢复历史分组或给出具体路线时，须增加相应结构，或者采用针对这些问题的其他算法。

参考：[1]