30-dars: DSU

4-darajaPlatina — dinamik programmalash25–32 darslar

HayotdaSinf

Sinfda bir necha do’stlik guruhi bor. Har kuni ikki o’quvchi do’st bo’ladi va ularning guruhlari qo’shilib ketadi. O’qituvchi har kuni bitta savol beradi: hozir nechta guruh qoldi? Har safar butun sinfni so’rab chiqish shart emas.

Bu darsdan keyin siz

• DSU ning ikki amalini yozasiz: topish va birlashtirish
• yo’lni siqish va o’lchamga qarab ulash nima berishini tushuntirasiz
• DSU qaysi masalalarda kerakligini taniysiz

Avval qo’lda

Avval qo‘lda

~7 daqiqa·guruh bilan·6 ta qog'oz varaqcha va ip (yoki chiziq)

Oltita varaqchaga 1 dan 6 gacha raqam yozing va stolga qo’ying. Har varaqchadan o’ziga strelka chizing — hozir har kim o’z guruhining vakili.

Endi «1 va 2 birlashdi» deyilsa, birining strelkasini ikkinchisiga qarating. «Kimning guruhidasan?» degan savolga strelkalar bo’ylab yurib javob bering.

Bir necha birlashtirishdan keyin strelkalar zanjiri uzayib ketadi. Endi qoidani o’zgartiring: javob topilgach, yo’lda uchragan hamma varaqchani to’g’ridan-to’g’ri vakilga qarating.

Nimani sezishingiz kerak

Ikkinchi qoida bilan zanjir uzayib ketmaydi: har so’rov uni kalta qilib qo’yadi. Bu — yo’lni siqish.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

DSU nima

DSUdisjoint set union

Bir-biri bilan kesishmaydigan guruhlarni saqlaydigan tuzilma. Ikki amali bor: element qaysi guruhda ekanini topish va ikki guruhni birlashtirish.

Har guruhning bitta vakili bo’ladi va har element vakiliga ko’rsatkich saqlaydi. Vakil o’zini ko’rsatadi.

eng sodda ko'rinishNusxalash

1n = 62ota = list(range(n + 1))3def topish(x):4  while ota[x] != x:5      x = ota[x]6  return x7ota[2] = 18ota[3] = 29print(topish(3), topish(1), topish(5))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 62ota = list(range(n + 1))3def topish(x):4  while ota[x] != x:5      x = ota[x]6  return x7ota[2] = 18ota[3] = 29print(topish(3), topish(1), topish(5))

Sizning bashoratingizTekshirish

Javobni ko'rish

1 1 5

3 dan 2 ga, 2 dan 1 ga — zanjir bo'ylab yurildi va vakil 1 topildi. 5 esa hali yolg'iz, shuning uchun o'zini ko'rsatadi.

Bu ko’rinish ishlaydi, lekin zanjir uzayib ketishi mumkin: n ta birlashtirish uzunligi n bo’lgan zanjir hosil qilsa, har so’rov O(n) turadi.

Sekin yechim

Masala: har birlashtirishdan keyin nechta guruh qolganini chiqaring. Birinchi fikr — har safar grafni boshidan kezib sanash.

sekin.pyNusxalash

1n = 62amallar = [(1, 2), (3, 4), (2, 3), (1, 4)]3qoshni = [[] for _ in range(n + 1)]4javoblar = []5for a, b in amallar:6  qoshni[a].append(b)7  qoshni[b].append(a)8  korilgan = [False] * (n + 1)9  guruhlar = 010  for boshi in range(1, n + 1):11      if korilgan[boshi]:12          continue13      guruhlar += 114      korilgan[boshi] = True15      stek = [boshi]16      while stek:17          u = stek.pop()18          for v in qoshni[u]:19              if not korilgan[v]:20                  korilgan[v] = True21                  stek.append(v)22  javoblar.append(guruhlar)23print(javoblar)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 62amallar = [(1, 2), (3, 4), (2, 3), (1, 4)]3qoshni = [[] for _ in range(n + 1)]4javoblar = []5for a, b in amallar:6  qoshni[a].append(b)7  qoshni[b].append(a)8  korilgan = [False] * (n + 1)9  guruhlar = 010  for boshi in range(1, n + 1):11      if korilgan[boshi]:12          continue13      guruhlar += 114      korilgan[boshi] = True15      stek = [boshi]16      while stek:17          u = stek.pop()18          for v in qoshni[u]:19              if not korilgan[v]:20                  korilgan[v] = True21                  stek.append(v)22  javoblar.append(guruhlar)23print(javoblar)

Sizning bashoratingizTekshirish

Javobni ko'rish

[5, 4, 3, 3]

Oxirgi amalda 1 va 4 allaqachon bitta guruhda edi, shuning uchun son o'zgarmadi. Yechim to'g'ri, lekin har amalda butun graf qaytadan kezildi.

Nega sekin

Har so’rovda butun graf kezib chiqiladi: q × (n + q) amal. Chegara esa n ≤ 10⁵, q ≤ 2 · 10⁵.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 200 000
Har amalda qayta kezishn^2	10⁶sig‘adi	10¹⁰sig‘maydi
DSUn	1 000sig‘adi	200 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

Ikkita hiyla zanjirni kalta saqlaydi. Birinchisi — yo’lni siqish: vakil topilgach, yo’lda uchragan hamma element to’g’ridan-to’g’ri vakilga ulanadi. Ikkinchisi — o’lchamga qarab ulash: kichik guruh kattasiga ulanadi, teskarisi emas.

tez.pyNusxalash

1n = 62ota = list(range(n + 1))3olcham = [1] * (n + 1)4def topish(x):5  ildiz = x6  while ota[ildiz] != ildiz:7      ildiz = ota[ildiz]8  while ota[x] != ildiz:9      ota[x], x = ildiz, ota[x]10  return ildiz11def birlashtir(a, b):12  ra, rb = topish(a), topish(b)13  if ra == rb:14      return False15  if olcham[ra] < olcham[rb]:16      ra, rb = rb, ra17  ota[rb] = ra18  olcham[ra] += olcham[rb]19  return True20guruhlar = n21javoblar = []22for a, b in [(1, 2), (3, 4), (2, 3), (1, 4)]:23  if birlashtir(a, b):24      guruhlar -= 125  javoblar.append(guruhlar)26print(javoblar)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 62ota = list(range(n + 1))3olcham = [1] * (n + 1)4def topish(x):5  ildiz = x6  while ota[ildiz] != ildiz:7      ildiz = ota[ildiz]8  while ota[x] != ildiz:9      ota[x], x = ildiz, ota[x]10  return ildiz11def birlashtir(a, b):12  ra, rb = topish(a), topish(b)13  if ra == rb:14      return False15  if olcham[ra] < olcham[rb]:16      ra, rb = rb, ra17  ota[rb] = ra18  olcham[ra] += olcham[rb]19  return True20guruhlar = n21javoblar = []22for a, b in [(1, 2), (3, 4), (2, 3), (1, 4)]:23  if birlashtir(a, b):24      guruhlar -= 125  javoblar.append(guruhlar)26print(javoblar)

Sizning bashoratingizTekshirish

Javobni ko'rish

[5, 4, 3, 3]

Javob bir xil. birlashtir allaqachon bir guruhda bo'lganlar uchun False qaytaradi — shuning uchun hisoblagich noto'g'ri kamaymaydi.

◆Asosiy g'oya

Ikki hiyla birga ishlatilganda har amal deyarli o’zgarmas vaqtda bajariladi. «Deyarli» degani — juda sekin o’sadigan funksiya, u amalda hech qachon 5 dan oshmaydi. Amaliy maqsadlarda buni o’zgarmas deb hisoblash mumkin.

Qaysi masalalarda kerak

DSU bitta savolga javob beradi: «bu ikkisi bir guruhdami?» — va guruhlar faqat qo’shiladi, hech qachon bo’linmaydi.

Shu ikki shart bajarilsa DSU ishlaydi: bog’langan guruhlar sonini kuzatish, halqa borligini aniqlash, MST qurish (31-dars). Guruhni ajratish kerak bo’lsa — DSU yaramaydi.

Sinab ko’r

Vizualda uch ustidagi son — uning guruhi vakili. Bir guruhdagilar bir xil sonni ko’rsatishini kuzating.

DSU — birlashtirish va topish

Uch ustidagi son — guruh vakili. Bir guruhdagilar bir xil sonni ko'rsatadi.

Har guruhning vakili bor; birlashtirishda kichik guruh kattasiga ulanadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Boshida har kim o'z guruhida yolg'iz: 6 ta guruh. Uch ustidagi son — uning guruhi vakili.
2. 1 va 2 birlashdi. Kichik guruh kattasiga ulandi, yangi vakil — 1. Guruhlar soni: 5.
3. 4 va 5 birlashdi. Kichik guruh kattasiga ulandi, yangi vakil — 4. Guruhlar soni: 4.
4. 2 va 3 birlashdi. Kichik guruh kattasiga ulandi, yangi vakil — 1. Guruhlar soni: 3.
5. 5 va 6 birlashdi. Kichik guruh kattasiga ulandi, yangi vakil — 4. Guruhlar soni: 2.
6. 3 va 4 birlashdi. Kichik guruh kattasiga ulandi, yangi vakil — 1. Guruhlar soni: 1.
7. 1 va 6 allaqachon bitta guruhda (vakili 1). Hech narsa o'zgarmaydi — bu qirra halqa hosil qilgan bo'lardi.
8. Hammasi bitta guruhda. Kichikni kattaga ulash qoidasi zanjirning uzayib ketishiga yo'l qo'ymaydi — shu sababli «vakiling kim?» degan savol deyarli bir qadamda javob oladi.

Boshida har kim o'z guruhida yolg'iz: 6 ta guruh. Uch ustidagi son — uning guruhi vakili.

Amal0

OrqagaO‘ynatishOldinga1/8Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

30 / 40

MasalaHar birlashtirishdan keyin guruhlar sonini chiqaring.

Taklif qilingan yechim

1. 1ota massivini o‘zi bilan boshlaymiz, guruhlar = n.
2. 2Har amalda a va b ning vakillarini topamiz.
3. 3ota[b] = a deb qo‘yamiz va guruhlar ni bittaga kamaytiramiz.
4. 4Har amaldan keyin guruhlar ni chiqaramiz.

Bu javobning 3-qismi noto'g'ri. Ikki xato bir qatorda. Birinchisi: ota[b] = a — VAKIL emas, elementning o'zi ulanmoqda; bu bor bog'lanishlarni buzadi. Ikkinchisi: ular allaqachon bir guruhda bo'lishi tekshirilmayapti, shuning uchun hisoblagich ortiqcha kamayadi. To'g'risi: ota[rb] = ra va faqat ra != rb bo'lganda.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1DSU ning ikki amali qanday?

Javobni ko'rish

topish(x) — x qaysi guruhda ekanini bilish, birlashtir(a, b) — ikki guruhni qo’shish.

2Yo'lni siqish nima qiladi?

Javobni ko'rish

Vakil topilgach, yo’lda uchragan hamma elementni to’g’ridan-to’g’ri vakilga ulaydi. Shuning uchun keyingi so’rovlar deyarli bir qadamda javob beradi.

3Nega kichik guruh kattasiga ulanadi?

Javobni ko'rish

Aks holda zanjir uzayib ketadi: har birlashtirishda chuqurlik bittaga oshaveradi. Kichikni kattaga ulash chuqurlikni logarifmik ushlab turadi.

4DSU qanday masalada YARAMAYDI?

Javobni ko'rish

Guruhlarni ajratish kerak bo’lganda. DSU faqat qo’shishni biladi: bir marta birlashgan guruhlarni qaytarib ajratib bo’lmaydi.

5birlashtir nega False qaytaradi?

Javobni ko'rish

Ular allaqachon bitta guruhda bo’lganini bildirish uchun. Shu javobga qarab guruhlar hisoblagichi kamaytiriladi yoki qoldiriladi.

Masalalar

Masalalar

3 ta

• Road ConstructionCSES 1676o'rta

  Darsdagi masalaning o‘zi, ustiga eng katta guruh o‘lchami ham so‘ralgan.

• Road ReparationCSES 1675o'rta

  Bu allaqachon MST — 31-darsning masalasi. DSU tayyor bo‘lgach u bir necha qatorga sig‘adi.

• Cut RibbonCodeforces 189Aoson

  Bu DSU emas, 1D DP (26-dars) — usulni chalkashtirmaslikni ham mashq qilish kerak.

Lokal mashq: mashqlar/30-guruhlar/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Oltita varaqcha bilan mashqni takrorlang, lekin bu safar o’lchamga qarab ulashni qo’llang: har safar kichik guruhni kattasiga ulang. Zanjirning eng katta uzunligi qanchaga yetdi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

30-guruhlar masalasini yeching. Takroriy birlashtirish bo’lgan testni ataylab yasang va yechimingiz to’g’ri javob berishini tekshiring.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Ikki hiylani alohida o’chirib ko’ring: faqat yo’lni siqish, faqat o’lchamga qarab ulash, ikkalasi ham yo’q. Uch variantni 200 ming amalda o’lchang va vaqtlarni jadvalga yozing.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim