DSU - Kesishmaydigan to‘plamlar tizimi

Kesishmaydigan to‘plamlar tizimi

Kirish

DSU (Disjoint Set Union) quyidagi imkoniyatlarni taqdim etadi: bizga bir nechta elementlar berilgan, ularning har biri dastlab alohida to‘plam hisoblanadi. DSU istalgan ikki to‘plamni birlashtirish amalini qo‘llab-quvvatlaydi va aniq bir element qaysi to‘plamda ekanini aniqlash imkonini beradi. Klassik variantda uchinchi amal ham kiritiladi — yangi elementdan to‘plam yaratish.

Shunday qilib, DSU interfeysi uchta funksiyadan iborat:

• make_set(x) — bitta element $x$ dan yangi to‘plam yaratadi.
• find_set(x) — element $x$ joylashgan to‘plamni topadi (odatda to‘plam liderini qaytaradi).
• union_sets(x, y) — $x$ va $y$ elementlarini o‘z ichiga olgan to‘plamlarni birlashtiradi.

Realizatsiya

Har bir to‘plamni ildizli daraxt ko‘rinishida tasvirlaymiz. Cho‘qqilar — bu to‘plam elementlari. Daraxt ildizi to‘plam lideri deb ataladi. Shunda har bir daraxt bitta to‘plamga mos keladigan daraxtlar o‘rmoni hosil bo‘ladi.

Ikki cho‘qqi bir to‘plamda bo‘ladi faqat va faqat ularning daraxtlari liderlari bir xil bo‘lsa.

Sodda yechim

parent massivini yaratamiz, bu yerda parent[x] — cho‘qqisining ajdodi (va ildiz uchun ).