本文主要是介绍月球美容计划之并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
情境
如果有这么一个问题，A和B是亲戚关系，B和C是亲戚关系，D和E是亲戚关系……等等前提。如果给出X，请问他和A是不是亲戚关系。
不仅仅局限于这个情境，如果有一个或者几个集合，我们知道每两个元素是属于同一个集合的，那么我们能不能判断任意两个元素的归属关系呢？这样就有了并查集。
原理
如果把每个元素看做一片叶子，那么，一棵树就可以看做是这个集合。
类似原理，我们可以把每个元素以“树枝”链接起来，那么，就形成一个完整树，而这个过程，就是并查集实现的过程。
优化（压缩路径）
是树就存在遍历问题，有遍历就存在优化问题，而对并查集这棵树来说，优化来源于树的深度，树越深，在遍历起来越费时间，因此如果把树的深度优化好，那么省时间不是一点半点的。
模板
int per[10000000];int fin (int a) //查{int r = a;while (r != per[r])r = per[r];while (r != per[a]) //优化，压缩路径{int t = per[a];a = per[a];per[t] = r;}return r;}
这篇关于月球美容计划之并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
