Union-Find
ইউনিয়ন-ফাইন্ড
Element-গুলোকে disjoint set-এ ভাগ করে রাখা structure — find বলে দেয় কে কোন set-এ, union দুই set জোড়া দেয়; প্রায় O(1) amortized।
also: disjoint set, dsu, disjoint set union
প্রতিটা set একটা rooted tree; root-ই representative।
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return xদুইটা heuristic একসাথে:
- Path compression — traverse করা node-দের সরাসরি root-এর তলায় বসানো
- Union by rank/size — ছোট tree-কে বড়টার তলায় জোড়া
দুটো মিললে n operation-এর sequence খরচ O(n·α(n)); α inverse Ackermann — বাস্তবে constant।
Kruskal-এর MST-তে cycle ধরতে, dynamic connectivity query-তে, image segmentation-এ — ছাড়া চলে না।