DSU — Visual Explanation¶

union-এ trees merge হতে দেখো, তারপর path compression দিয়ে find কীভাবে সেগুলো flatten করে দেখো। সবসময় দুটো view: forest-এর drawing আর তার নিচে parent array।

এই file যে skill-টা গড়ে: যেকোনো parent array দিলে তুমি forest আঁকতে পারবে — আর যেকোনো forest দিলে array লিখতে পারবে। প্রতিটা frame পেন্সিল দিয়ে trace করো আর দুটো view sync-এ রাখো।

Part 1 — Union operations: trees merge করা¶

ছয়টা element, সবাই একা। Roots-দের * দিয়ে চিহ্ন দেওয়া (একটা root নিজেকেই point করে)।

Frame 0 — ছয়টা singleton tree¶

forest:   *0    *1    *2    *3    *4    *5

parent:  [ 0,    1,    2,    3,    4,    5 ]
size:    [ 1,    1,    1,    1,    1,    1 ]     groups: 6

Frame 1 — union(0, 1)¶

Roots হলো 0 আর 1। Sizes সমান (1 vs 1), তাই আমাদের tie rule অনুযায়ী first argument-এর root জেতে: 1, 0-এর নিচে ঝোলে।

forest:   *0      *2    *3    *4    *5
           |
           1

parent:  [ 0,  0,  2,  3,  4,  5 ]
size:    [ 2,  1,  1,  1,  1,  1 ]               groups: 5

Frame 2 — union(2, 3)¶

ঘরের অন্য পাশে একই গল্প।

forest:   *0      *2      *4    *5
           |       |
           1       3

parent:  [ 0,  0,  2,  2,  4,  5 ]
size:    [ 2,  1,  2,  1,  1,  1 ]               groups: 4

Frame 3 — union(1, 3): গুরুত্বপূর্ণটা¶

আমরা দুটো non-root union করছি। Algorithm কিন্তু 1 আর 3-কে সরাসরি ছোঁয় না:

step a:  find(1) -> walk 1 -> 0.  Root: 0
step b:  find(3) -> walk 3 -> 2.  Root: 2
step c:  sizes: size[0]=2, size[2]=2 — tie, so root 2 hangs under root 0

forest:        *0           *4    *5
              /  \
             1    2
                  |
                  3

parent:  [ 0,  0,  0,  2,  4,  5 ]
size:    [ 4,  1,  2,  1,  1,  1 ]               groups: 3

পুরো {2, 3} tree-টা তুলে নিয়ে ঝুলিয়ে দেওয়া হলো — ঠিক একটা array cell (parent[2] = 0) re-point করে। এজন্যই union সস্তা: যেকোনো size-এর groups merge করা মানে একটা pointer write (দুটো find-এর পরে)।

Frame 4 — union(4, 5), তারপর union(5, 0): size rule কাজে¶

union(4, 5)-এর পরে: 5, 4-এর নিচে ঝোলে (parent[5] = 4, size[4] = 2, groups: 2)।

এবার union(5, 0): roots হলো 4 (size 2) আর 0 (size 4)। ছোটটা বড়টার নিচে ঝোলে — 4 চলে যায় 0-এর নিচে:

forest:           *0
                / | \
               1  2  4
                  |  |
                  3  5

parent:  [ 0,  0,  0,  2,  0,  4 ]
size:    [ 6,  1,  2,  1,  2,  1 ]               groups: 1

যদি বদলে 0-কে 4-এর নিচে ঝোলাতাম, চারটা node (0,1,2,3) প্রত্যেকে এক step গভীরে নেমে যেত। size rule নাড়ালো মাত্র দুটো (4,5)। ছোটটাই নড়ার খরচ দেয় — এটাই পুরো union-by-size idea, আর এটা tree height-কে মোটামুটি log2(n)-এ আটকে রাখে।

Part 2 — path compression সহ find: flatten হওয়া¶

compression কেন দরকার সেটা দেখতে ইচ্ছে করে একটা খারাপ chain বানাও। এমন unions-এর পরে যা তৈরি করে:

forest:    *0                    parent: [0, 0, 1, 2, 3]
            |
            1
            |
            2
            |
            3
            |
            4

Frame A — find(4), উপরে হাঁটা (before)¶

walk:  4 -> 3 -> 2 -> 1 -> 0*        4 hops to the root

compression ছাড়া, ভবিষ্যতের প্রতিটা find(4) ওই 4 hop আবার শোধ করে। দশ লাখ element হলে, এরকম chains DSU-কে linked-list scan-এর মতো ধীর বানিয়ে দেয়।

Frame B — একই find, compression সহ (after)¶

Path compression হাঁটা path-এর প্রতিটা node-কে সরাসরি root-এ re-point করে:

BEFORE                       AFTER find(4) with compression

   *0                            *0
    |                          / | | \
    1                         1  2 3  4
    |
    2          parent before: [0, 0, 1, 2, 3]
    |          parent after:  [0, 0, 0, 0, 0]
    3
    |
    4

Tree-টা snap করে flat হয়ে গেল। 1, 2, 3, বা 4-এর উপর ভবিষ্যতের প্রতিটা find এখন ঠিক এক hop। লম্বা হাঁটার খাটুনিটা ছিল একটা investment, যা পরের প্রতিটা query শোধ করে দেয় — amortized "পায়ে-হাঁটা পথ পাকা রাস্তা হয়ে যায়" effect।

Frame C — compression শুধু যে path-এ হাঁটে সেটাই flatten করে¶

একটা জরুরি সততা: হাঁটা path-এর বাইরের nodes নড়ে না। এই tree থেকে:

       *0
       / \
      1   2
      |
      3        parent: [0, 0, 0, 1]
      |
      4        parent[4] = 3

find(4) হাঁটে 4 → 3 → 1 → 0 আর ওই তিনটাকে flatten করে; node 2-কে কখনো visit করা হয়নি, সে যেখানে ছিল সেখানেই থাকে:

        *0
      / | | \
     1  2 3  4         parent: [0, 0, 0, 0, 0]

(এখানে 2 আগে থেকেই root-কে point করছিল, তাই ছবিটা ঘটনাচক্রে পুরো flat-এ শেষ হয় — কিন্তু শুধু এজন্য যে 2 আগে থেকেই ওখানে ছিল। Compression অলস: রাস্তা যেমন যেমন চালানো হয় তেমন তেমন ঠিক করে, পুরো map একসাথে না।)

code-এর "path halving" নিয়ে একটা note¶

implementation.py-র iterative find path halving ব্যবহার করে — হাঁটার সময় visit করা প্রতিটা node-কে তার grandparent-এ re-point করা হয়:

while parent[x] != x:
    parent[x] = parent[parent[x]]    # skip a generation
    x = parent[x]

এক pass, কোনো recursion নেই, আর প্রতি find-এ chain-এর length অর্ধেক হয়। দু-একটা find-এর পরে এটা full compression-এর মতোই flat। Frame B full compression এঁকেছিল কারণ ওটা পরিষ্কার mental picture; দুটোই একই near-constant amortized bound উপভোগ করে।

Part 3 — union(x, y) শুরু থেকে শেষ, একটা combined trace¶

parent = [0, 0, 0, 2, 4, 4] থেকে (groups {0,1,2,3} আর {4,5}), union(3, 5) চালাও:

step 1: find(3): walk 3 -> 2 -> 0.   halving sets parent[3] = 0.   root rx = 0
step 2: find(5): walk 5 -> 4.        root ry = 4
step 3: rx != ry  -> real merge.  size[0]=4 > size[4]=2 -> 4 hangs under 0

        *0
      / | | \
     1  2 3  4        parent: [0, 0, 0, 0, 0, 4]
             |
             5        groups: 1

খেয়াল করো 5 এখনো 4-কে point করে, root থেকে দুই hop দূরে — একদম ঠিক আছে। পরের find(5) এটাকে compress করবে। DSU কখনো তাড়াহুড়ো করে না; অলসভাবে গুছিয়ে নেয় আর তবু প্রতি operation-এ near-O(1)-তেই থাকে।

নিজে চেষ্টা করো¶

ছয়টা singleton থেকে শুরু করে union(2,4), union(0,2), union(3,5), union(4,5) করো। প্রতিবারের পরে forest + parent array আঁকো। কয়টা group থাকে? (উত্তর: 2।)
array-তে হাতে chain 0←1←2←3 বানাও, তারপর full compression সহ find(3) চালাও। array-টা before আর after লেখো।
exercise 1-এর final state-এ, কোন একটা union call False return করবে? membership rule দিয়ে ব্যাখ্যা করো।
parent = [1, 2, 2, 2, 3] নাও আর forest আঁকো। তারপর path halving সহ find(0) চালাও আর নতুন array লেখো। (Walk: 0→1→2; halving 0-কে 2-তে repoint করে।)

Interactive version: VisuAlgo-র Union-Find module। Reference: cp-algorithms DSU।