radoslav11's blog

Persistent DSU/Union find?
By radoslav11, history, 9 years ago, In English

Hello codeforces,

I was solving this problem:

You are given a graph, and you have to answer queries of type:
1) Delete edge from U to V
2) Add edge from U to V
3) See if vertexes U and V are in the same connected component.

I couldn't come with an online solution, but I think I found an offline one.

So first I compress all queries of adding or removing and edge as: edge from U to V is available in time [i; j], where i is the time of adding and j is time of removing. Now we can do divide and conquare with dsu. This will be like that:

Rec(L, R, dsu)
{
    Look for all queries that are q.L <= L and R <= q.R
    ([L; R] lies in [q.L; q.R]) and add unite q.U and q.V in dsu

    IF L == R -> if query[L] is of type 3 then answer it and stop (and also undo changes to dsu).

    Mid = (L + R) / 2;
    Rec(L, Mid, dsu);
    Rec(Mid + 1, R, dsu);

    Undo changes to dsu
}

So this solution is O(M*logM*Cost_of_dsu). But the problem is in the DSU (the undoing of operations). I couldn't find how to do persistent DSU or DSU with restoring/undoing/backtracking. So if someone knows how to do this I will really appriciate if he helps! :)

PS: By DSU I mean disjoint set union

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

You may consult this.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The main idea it to have a stack of changes in dsu's arrays that have been done. In the begining of rec you remember stack size. In the end of rec, you undo operation from top of the stack while it's size is not equal to size at the beginning. The only important thing that you sholdn't do pathes compression because it have amortized complexity, so it can't be used for persistent structure. After that dsu complexity will become O(logn)

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Here is an implementation of offline DSU.

→ Reply