Блог пользователя bloodoath

Path compression upon union in DSU
Автор bloodoath, история, 2 года назад, По-английски

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

Теги dsu
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      → Ответить
    • »
      »
      »
      2 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      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.

      → Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить