DSU — group জোড়া দেওয়া ও পথ ছোট করা¶

অধ্যায়ের সূচি · সহজ ব্যাখ্যা ও বাস্তব ব্যবহার · অনুশীলন ও সমাধান

DSU-তে parent[x] বলে x থেকে root খুঁজতে পরের কোন node-এ যাব। Root নিজেকেই parent বলে। Union দুই root-কে জোড়ে; find root খুঁজে এবং চলার পথ ছোট করতে পারে।

Union — ছয়টি group থেকে একটি¶

শুরুতে 0–5 প্রত্যেকেই আলাদা root। ছোট group-কে বড়টির নিচে রাখব। Size সমান হলে এই উদাহরণে প্রথম argument-এর root জিতবে। বাক্সের index হলো element; ভেতরের value হলো তার parent।

প্রতিটি union-এর পরে সম্পূর্ণ parent array

শুরু — 6টি group
00
11
22
33
44
55
প্রত্যেকে নিজেই root; প্রতিটি group-এর size 1।
union(0, 1) — 5টি group
00
চিহ্নিত ঘর: 10
22
33
44
55
Size সমান। parent[1] = 0; root 0-এর size এখন 2।
union(2, 3) — 4টি group
00
10
22
চিহ্নিত ঘর: 32
44
55
parent[3] = 2; root 2-এর size এখন 2।
union(1, 3) — 3টি group
00
10
চিহ্নিত ঘর: 20
32
44
55
Roots 0 ও 2। দুই group-এর size 2; parent[2] = 0, size[0] = 4।
union(4, 5) — 2টি group
00
10
20
32
44
চিহ্নিত ঘর: 54
parent[5] = 4; root 4-এর size এখন 2।
union(5, 0) — 1টি group
00
10
20
32
চিহ্নিত ঘর: 40
54
Roots 4 ও 0। Size 2 < 4, তাই parent[4] = 0; size[0] = 6।

union(1,3)-তে সরাসরি 1-এর সঙ্গে 3 জোড়া হয় না। আগে find(1) পথে 1 → 0, আর find(3) পথে 3 → 2 যায়। তারপর root 2-এর parent বদলায়। তার নিচে থাকা 3 নিজে না সরেও একই group-এর অংশ হয়ে যায়।

শেষ forest নিচে। Arrow child থেকে parent-এর দিকে; root-এর self-loop আঁকা হয়নি।

flowchart BT
  n1((1)) --> n0["0 · root · size 6"]
  n2((2)) --> n0
  n4((4)) --> n0
  n3((3)) --> n2
  n5((5)) --> n4

Union-এর পরে	সম্পূর্ণ size array	অর্থপূর্ণ root size
শুরু	`[1,1,1,1,1,1]`	সবাই 1
`(0,1)`	`[2,1,1,1,1,1]`	0-এর size 2
`(2,3)`	`[2,1,2,1,1,1]`	0 ও 2-এর size 2
`(1,3)`	`[4,1,2,1,1,1]`	0-এর size 4
`(4,5)`	`[4,1,2,1,2,1]`	0-এর size 4, 4-এর size 2
`(5,0)`	`[6,1,2,1,2,1]`	শুধু 0-এর size 6

Non-root-এর পুরোনো size মুছে দেওয়া হয়নি; সিদ্ধান্ত নিতে শুধু root-এর size ব্যবহার করি। ছোট group বড়টির নিচে গেলে ছোট group-এর node-গুলোর depth এক বাড়ে। কোনো node-এর depth বাড়ার জন্য তার group-এর size অন্তত দ্বিগুণ হয়; তাই compression ছাড়াও height O(log n) থাকে।

Full path compression — একই root, ছোট পথ¶

বোঝানোর জন্য এবার আলাদা একটি দীর্ঘ chain নিই: parent = [0,0,1,2,3]। এটি আগের union-by-size ধাপগুলোর ফল নয়। find(4) প্রথমে 4 → 3 → 2 → 1 → 0 যায়—চারটি edge। Full compression সেই পথের node-গুলোকে সরাসরি 0-এর সঙ্গে জুড়ে দেয়।

flowchart BT
  subgraph before["আগে: find(4)-এ 4টি edge"]
    b4((4)) --> b3((3)) --> b2((2)) --> b1((1)) --> b0["0 · root"]
  end
  subgraph after["পরে: find(4)-এ 1টি edge"]
    a1((1)) --> a0["0 · root"]
    a2((2)) --> a0
    a3((3)) --> a0
    a4((4)) --> a0
  end

Full compression-এর আগে ও পরে

আগে
00
10
21
32
43
Root-এ পৌঁছাতে 4 থেকে চারটি parent pointer অনুসরণ করতে হয়।
find(4)-এর পরে
00
10
চিহ্নিত ঘর: 20
চিহ্নিত ঘর: 30
চিহ্নিত ঘর: 40
2, 3 ও 4-এর parent বদলেছে। 1 আগেই root-কে point করছিল।

Compression শুধু যে পথে যায় সেই path বদলায়। উদাহরণ: [0,0,0,1,3] থেকে find(4) পথ 4 → 3 → 1 → 0 ছোট করে; node 2-তে যায় না। ফল [0,0,0,0,0] পুরো flat দেখালেও 2 আগে থেকেই root-এ ছিল। অন্য শাখা থাকলে সেটি নিজে থেকে flat হতো না।

Implementation-এ path halving¶

implementation.py-র iterative find full compression-এর বদলে path halving করে: বর্তমান node-কে তার grandparent-এর সঙ্গে জোড়ে, তারপর সেই grandparent-এ যায়।

Python

while parent[x] != x:
    parent[x] = parent[parent[x]]
    x = parent[x]

দুই পদ্ধতির ফল এক pass-এ একরকম নাও হয়। একই chain-এ find(4) দিয়ে পার্থক্য দেখো:

পদ্ধতি	`parent` শুরু	একটি `find(4)` শেষে	4 থেকে root-এর পথ
Full compression	`[0,0,1,2,3]`	`[0,0,0,0,0]`	`4 → 0`
Path halving	`[0,0,1,2,3]`	`[0,0,0,2,2]`	`4 → 2 → 0`

Halving-এ প্রথমে parent[4]=2, এরপর parent[2]=0 হয়। পরের find পথ আরও ছোট করতে পারে। Union-by-size-এর সঙ্গে দুই পদ্ধতিরই amortized সময় O(α(n)), যা ব্যবহারিক input-এ খুব ছোট।

Find ও union একসঙ্গে — `union(3,5)`¶

শুরু parent = [0,0,0,2,4,4]। Groups {0,1,2,3} ও {4,5}। এবার path halving ব্যবহার করি।

ধাপ	কাজ	ফল
1	`find(3)` পথে `3 → 2 → 0`	`parent[3]=0`; root 0
2	`find(5)` পথে `5 → 4`	root 4; parent বদলায় না
3	Size 4 ও 2 তুলনা	ছোট root 4-কে 0-এর নিচে রাখি
4	Group count কমাই	2 থেকে 1

flowchart BT
  n1((1)) --> n0["0 · root · size 6"]
  n2((2)) --> n0
  n3((3)) --> n0
  n4((4)) --> n0
  n5((5)) --> n4

শেষ parent array [0,0,0,0,0,4]। 5 এখনো 4-কে point করে—এটি ভুল নয়। Union-এর পরে পুরো tree আবার flatten করার দরকার নেই; পরের find(5) তার পথ ছোট করবে।

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

ছয়টি singleton থেকে union(2,4), union(0,2), union(3,5), union(4,5) করো। প্রতিবার parent array লেখো। শেষে 2টি group থাকবে।
Chain 0 ← 1 ← 2 ← 3-এ full compression সহ find(3) করে আগে-পরে array লেখো।
প্রথম অনুশীলনের final state-এ কোন union নতুন group জোড়া দিতে পারবে না? Root দিয়ে ব্যাখ্যা করো।
parent = [1,2,2,2,3]-এ path halving সহ find(0) করলে কোন cell বদলায়?

চলমান উদাহরণ: VisuAlgo Union-Find। আরও পড়া: cp-algorithms DSU।