[算法] 并查集

并查集维护元素的分组情况，可以处理不相交集合的合并及查询问题，用于求解图的连通等问题。

并查集使用树型结构实现（但并不是二叉树后面会说明原因），构建过程为：

初始化
合并时从一组的根向另一组连边
为防止合并时出现树的退化（类似平衡二叉树），对每棵树记录树高（rank），合并时从rank小向rank大的树连边。
合并
判断两节点的根是否相同查询是否为同组元素
为提高查询的效率，进行路径压缩：每个节点一旦查询到根节点就将其父节点直接指向根节点，但为简化问题即使树高改变也不修改rank。
查询

并查集的实现：
两个数组（父亲节点par[]、树高rank[]），两个函数（find、union）

例题：

1. CLRS 16-4 单位时间任务调度问题

将输入的任务序列按惩罚值单调递减顺序排序后，实现算法时要解决的主要问题是查找指定的空时间槽。假设时间槽为数组T，初始化数组T为空，每次当我们需要向T的位置k插入一个任务时，如果T[k]为空直接插入即可，如果T[k]不为空，我们需要找到最大的i满足且T[i]为空，将其插入位置i；如果i不存在返回-1。如果将被安排在数组T中相邻位置的连续任务放入同一集合，数组T可分为多个不相交的集合，如下图所示：

问题的不相交集合表示

查找满足条件的最大的i的过程即使用并查集查找各集合根节点的过程。并查集包括make_set, find_set, union三个操作。实现并查集的结构时需要维护一个par数组存放并查集各集合元素的父节点，make_set时遍历数组将par[i]初始化为i，之后par[i]存放数组T中i位置的前一个被连续插入任务的位置以便向前进行查找，但这样查询效率并不高，为提高查找效率，采用路径压缩，即对于每个位置i，当该位置一旦查询了一次前面为空的最大可插入位置，就将其par[i]直接指向该位置，从而实现查询路径压缩。在实现union方法进行合并时注意按秩合并避免出现树的退化。略去并查集的具体实现，问题的核心伪码如下所示，求解结果通过序列A的scheduledTime属性返回。

SCHEDULE_TASK(A)
    n = A.length
    init empty array T of size n
    make_set(n)
    // 序列A从1开始   
    for i from 1 to n
        if (T[A[i].deadline] != NULL)
            pos = find_set(T[A[i].deadline])
            if (pos == -1)
                pos = find_set(T[n])
        else 
            pos = A[i].deadline;
        A[i].scheduledTime = pos
        T[pos] = I;
        if (T[pos - 1] != NULL)
            union(T[pos - 1], T[pos])
        if (T[pos + 1] != NULL)
            union(T[pos + 1], T[pos])