并查集（不相交集）的路径平分

路径平分（path halving）

通过使在从$i$i到根的路径上的每一个其他节点指向它的祖先（存在时）以实现对$Find(i)$Find(i)的偏路径压缩（partial path compression）。这叫做路径平分（path halving）。

一开对其性质理解的不够深，弄不清楚到底是从$X$X本身开始指向祖父，还是从$X$X的父节点才开始指向祖父，到最后$X$X是否连接在根上；到后来才弄清楚，执行$Find(X)$Find(X)时，就从$X$X开始指向其祖父，并且一路到根节点。

如下图所示，执行路径平分查找前后对比：

代码

SetType Find1(ElementType X, DisjSet S)
{
    while (S[X] > 0 && S[S[X]] > 0)
    {
        S[X] = S[S[X]];
        X = S[X];
    }
    if (S[X] > 0)
        X = S[X];
    return X;
}