并查集

　　首先假设一个情景，一个班级上有很多学习小组，假如Alice，Amy等以A为首字母的属于一个小组，Bob，Ben等以B为首字母的属于一个小组，以此类推。 我们如果想快速查询任意两个人是否属于一个集合（不以首字母为依据），或者将两个学习小组合并为一个，用何种数据结构去组织最快呢。并查集是一种轻量级的数据结构，其本质是一种集合，支持不相交集合的“并”和“查”的操作。由于在特定状况下，可以通过某些特殊处理将这两种操作的时间复杂度降至很低，所以在某些算法，例如tarjan求lca的实现中，也引入了这一数据结构。

基本实现

　　其实并查集的本质就是一个划分，商集中的每一个元素（集合）内的元素都可以建一棵树，放在一起就变成了森林。对于任意两个个元素，只需要看他们的树根是否相等，就可以判断他们是否属于同一集合；至于两个集合的合并，只需要将一棵树的树根指向另一棵树的树根。那么，可以用pre[i]记录i这个结点的父节点，初始化时只需令pre[i] = i，意味着每一个结点都属于一个单独的集合，也就是每一个节点都是树根。如果想查找树根怎么办呢？ 按照定义pre[i]是i的父亲，pre[pre[i]]就是i结点父亲的父亲，按照这个方式不断向上找直至pre[i]等于i，就找到了树根，可以使用递归来实现。如果想合并两个集合怎么办呢，只需要找到两个元素所在树的树根，将一个树根指向另一个，就完成了。

时间复杂度优化

启发式合并

　　为了解决合并时树退化成链的情况，在合并时我们可以根据两棵树的深度合并，将最大深度小的向最大深度大的合并。如果两棵树的深度一样，则随便选一个作为根，并将根的最大深度+1。这样做的话在n次操作后，任何一棵树（一个集合）的深度最大不会超过[logn]+1，从而使查找的时间复杂度降为$O(logn)$。代码如下：

int merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
        if (rank[rx] == rank[ry]) {
            pre[ry] = rx;
            rank[rx]++;
        }
        else if (rank[rx] < rank[ry]) {
            pre[rx] = ry;
        }
        else {
            pre[ry] = rx;
        }
    }
}

路径压缩

　　一般情况下我们只需要知道知道一个元素所在的树的根就可以，所以可以在查找元素的过程中，把路径上的所有子节点直接指向根节点，这样就可以将查找的复杂度降至O(1)。代码如下：

int find(int x) {
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}

应用时的问题

　　在具体问题中，两棵树是否可以按秩合并，以及是否可以路径压缩是需要按照题的要求来定的，本文只是提出了大体框架及基本实现（可移步我的github查看）。具体节点信息的维护或是节点合并顺序等还需要自己判断。