একটি disjoint-set (union-find) ক্রমাগত অ-অতিক্রমকারী গোষ্ঠীতে বিভক্ত উপাদান ট্র্যাক করে এবং "এই দুটি একই গোষ্ঠীতে আছে?" এবং প্রশ্নের উত্তর দেয় । এবং সহ, উভয় অপারেশন তে চলে — কার্যকরভাবে O(1) (α হল Ackermann ফাংশনের বিপরীত)।
একটি disjoint-set (union-find) ক্রমাগত অ-অতিক্রমকারী গোষ্ঠীতে বিভক্ত উপাদান ট্র্যাক করে এবং "এই দুটি একই গোষ্ঠীতে আছে?" এবং প্রশ্নের উত্তর দেয় । এবং সহ, উভয় অপারেশন তে চলে — কার্যকরভাবে O(1) (α হল Ackermann ফাংশনের বিপরীত)।
প্রতিটি সেট একটি গাছ; রুট হল সেটের প্রতিনিধি। find রুটের দিকে হাঁটে; union একটি রুটকে অন্যটির অধীনে সংযুক্ত করে।
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
before: a->b->c->root after: a->root, b->root, c->root
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0]*n
def find(self, x): # path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # halve path
x = self.parent[x]
return x
def union(self, a, b): # union by rank
ra, rb = self.find(a), self.find(b)
if ra == rb: return False
if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
return True
| অপারেশন | সময় (উভয় অপ্টিমাইজেশন সহ) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |
Union-find গ্রুপিং এবং সংযোগ সমস্যা সমাধান করে যা অন্যথায় পুনরাবৃত্তিমূলক O(n) গ্রাফ ট্রাভার্সাল প্রয়োজন হবে, তাদের প্রতিটি প্রশ্নে প্রায় O(1) এ পরিণত করে।
যখনই আপনাকে ক্রমবর্ধমান সেট একত্রিত করতে এবং সংযোগযোগ্যতা পরীক্ষা করতে হয় তখন এটি একটি যাওয়ার টুল — একটি ঘন ঘন সিনিয়র-স্তরের সাক্ষাত্কার বিষয়।