多请求有向无环图中的高效根查找

Question

我正在努力找到一个时间复杂度为o（mlogn）+o（n）的解决方案

Assume you have directed acyclic graph with n nodes and m requests, each node has at most one parent. At time = 0, the graph is empty. Requests have two types: add edge (u, v) or find root of the subgraph with vertex u. You should add edges only if it doesn't break any property of the graph (it should remain acyclic and each node should still have at most one incoming edge).

我可以想到多种解决方案，但它们都没有所需的复杂性。这里我描述了我的最佳解决方案（复杂性方面）。创建向量根（根[u]是具有顶点u的子图的根）和向量子图的向量（子[u]是顶点u的后代）。添加边（u，v）后，我将按以下方式更新向量：

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

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

你能就如何解决这个问题提出一些建议吗？我假设一定有一个O（m log^2n+n）解

Answer 1

这可以通过使用路径压缩的联合查找来完成，但不需要按秩联合，因为能够控制哪个节点仍然是其组件的根非常重要。时间复杂度如所需，O（m logn+n）