CODEWITHSUNDEEP
pythonc++algorithmtreedirected-acyclic-graphs
user123213
user123213

Reputation: 33

Efficient root finding in directed acyclic graph for multiple requests

I'm struggling to find a solution to this problem with time complexity o(m log n) + 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).

There are multiple solutions I could think of, but neither of them has the required complexity. Here I describe my best solution (complexity-wise). Create vector roots (roots[ u ] is a root of subgraph with vertex u) and vector of vectors children (children[ u ] are descendants of vertex u). After edge (u, v) is added, I update vectors the following way:

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

This way, checking whether adding edge breaks the property or returning root takes O(1) time. However, updating procedure has total complexity O(n^2) (there can be at most n - 1 edges in such graph and children[ u ] has size at most n - 1 for every u). The total complexity is O(m + n^2).

Could you please suggest any ideas on how to solve it? I assume that there must be a O(m log^2 n + n) solution.

Upvotes: 1

Views: 253

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

This can be done by union find with path compression, but without union by rank since it's important to be able to control which node remains the root of its component. The time complexity is as desired, O(m log n + n).

Upvotes: 1

Related Questions