有向无环图中多重请求的有效求根

Question

我正在努力寻找一个时间复杂度为o（m log n)+o(n)的问题的解决方案。

假设有向无环图有n个节点和m个请求，每个节点最多有一个父节点。在时间=0时，图为空。请求有两种类型：添加边(u，v)或查找顶点为u的子图的根。只有在不破坏图的任何属性的情况下才应该添加边（它应该保持无循环，每个节点最多仍然应该有一条传入边）。

for child in children[v]:
    root[child] = u
    children[u].append(child)
children[v] = []

这样，检查添加edge是否破坏属性或返回root需要O(1)个时间。然而，更新过程的总复杂度为O(n^2)（在这样的图中最多可以有n-1条边，每个u的子图[u]的大小最多为n-1）。总复杂度为O(m+n^2)。

你能就如何解决这个问题提出一些想法吗？我假设一定存在一个O(m log^2n+n)解。

Answer 1

这可以通过使用路径压缩的联合查找来实现，但不使用按等级的联合，因为能够控制哪个节点仍然是其组件的根是很重要的。时间复杂度为O(m log n+n)。