bloodoath's blog

Path compression upon union in DSU
By bloodoath, history, 20 months ago, In English

Given, two disjoint sets with roots 1 and 6 respectively which already have their childrens' paths compressed.

I wish to do a union but instead of

this

I want

this

Unable to figure out a way to do this optimally.

DSU I am using is on cp-algorithms

Tags dsu
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

On the cp-algorithms page there is an example of this under the title "Storing the DSU explicitly in a set list".

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It will also return the first form and it still requires me to run a recursive find_set once to achieve the second form from the first, which will give me O(n^2) in the worst case. I guess there is no way, I should probably give it up for now. Thanks for your comment.

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why should it? Let's do the following.

      We maintain the invariant that after any merge operation, every single component is a star graph (I hope that is what you meant).

      Let's maintain the sizes of every component in a array called sz, and for each "representative", a vector of all the vertexes that belong to him (let it be g). Now, we use the small-to-large technique — when we merge components with representative P_a and representative P_b, (|P_a| > |P_b|), we simply iterate over all vertexes in g[P_b], add them to g[P_a], increase the size of P_a by |P_b|, and directly link them, thus maintaining the invariant. As every time a vertex gets redirected, the size increases at least two times, each vertex will be merged no more than O(NlogN) times, and we get a runtime ofO(NlogN + Q)

      → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I'm not sure what you mean, you can directly create the graph you wanted from the lst array?

      The first picture would have two non-empty entries in lst:

      lst[1] = [1,2,3,4]
lst[6] = [6, 5, 8, 7]

      You then merge any node in lst[1] with any node in lst[6] and you'll end up with one item in the list:

      lst[1] = [1,2,3,4,5,6,7,8].

      Every node will also have parent[x] = 1.

      It looks like the worst case complexity is bad but small to large merging ensures that it isn't O(n^2) as each item would only be moved at most log n times.

      → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Thank you induk_v_tsiane and robostac for the explanation. I didn't notice the fact that each item doesn't get moved more than log(n) times.

      → Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think you mean this:

int get(int a){
    if (a != p[a]){
        p[a] = get(p[a]);
    }
   return p[a];
}

void unio(int a, int b){
    a = get(a);
    b = get(b);
    if (a != b){
    	if (s[a] > s[b]) swap(a, b);
    	p[a] = b;
   	s[b] += s[a];
   }
}

You can check how this code works in EDU : DSU, pretty useful. Hope i helped

→ Reply