（深度确定）在深度确定（depth determination）问题中，我们通过以下三个操作来维护一个有根树的森林F={Ti}:
MAKE-TREE(v):创建一棵只包含唯一节点v的树
FIND-DEPTH（v）:返回节点v在树中的深度
GRAFT(r,v):使得节点r（假定它是一棵树的树根）成为节点v的孩子（假定它在另一棵树中，但是它本身可能是，也可能不是一棵树的树根）
a.假设采用类似于不相交集合森林的树表示：我们可以通过置r.p=v来实现 GRAFT(r,v)，并且可以通过沿着查找路径上升至根。返回一个除v以外的节点数来实现 FIND-DEPTH（v）操作。证明：一组m个MAKE-TREE,FIND-DEPTH和GRAFT操作的序列的最坏情况运行时间是)
。
通过使用按秩合并与路径压缩启发式策略，能减少最坏情况运行时间，我们使用不相交集合森林
={Si}，其中每个集合Si（它本身是一棵树）对应于一棵森林F中的树Ti，然后集合Si中的树结构没有必要对应于Ti的树结构。实际上，Si的实现并没有记录准确的父子关系，但它允许我们确定Ti中任意节点的深度。
关键的思想是维护每个节点v的一个伪距离v.d，它被定义为使得沿着从v到它的集合Si的根的简单路径上的伪距离之和等于Ti中节点v的深度。也就是说，从v到它在Si的根的简单路径为v0,v1,..,vk（这里v0=v并且vk是Si的根），那么节点v在树Ti上的深度为
。
b.给出MAKE-TREE的一种实现。
c.说明应如何修改FIND-SET来实现FIND-DEPTH。你的实现要采用路径压缩，并且它的运行时间应与查找路径的长度呈线性关系。试确保你的实现能正确的更新伪距离。
d.说明如何实现GRAFT(r,v)，它通过修改UNION和LINK过程来合并包含r和v的集合。试确保你的实现能正确的更新伪距离。并注意到，集合Si的根没有必要是对应树Ti的根。
e.试给出一组m个MAKE-TREE,FIND-DEPTH和GRAFT操作的序列（其中n个是MAKE-TREE操作）最坏情况运行时间的一个紧确界。
MAKE-SET(v){
x.p = x
x.rank = 0
}
UNION(u,v){
LINK(FIND-SET(u),== FIND-SET(v))
}
LINK(x,y){
if x.rank > y.rank
y.p = x
else
x.p = y
if x.rank == y.rank
y.rank++
}
FIND-SET(x){
if x != x.p
x.p = FIND-SET(x.p)
return x.p
}
