Asosiy mazmunga o'tish
STEAM AcademySTEAM Academy

22-dars: Topologik saralash

3-darajaOltin — graflar17–24 darslar

Bu darsdan keyin siz

  • yo’naltirilgan grafda bog’liqlik tartibini quryasiz
  • kiruvchi daraja tushunchasini ishlatasiz
  • siklni aniqlaysiz va nega tartib imkonsiz ekanini tushuntirasiz

Avval qo’lda

“Avval qo’lda” bo'limiga havola

Avval qo‘lda

~5 daqiqajuftlikdaQog'oz va qalam

Kiyinish tartibini graf qilib chizing: paypoq, oyoq kiyim, ko’ylak, svitr, shim, kamar. Strelka «bundan oldin kiyiladi» degani.

Endi to’g’ri tartibni toping. Qoida bitta: hech qanday strelka kirmayotgan narsani oling, ro’yxatga yozing va uni chizmadan o’chiring. Takrorlang.

Nimani sezishingiz kerak

Ba’zi qadamlarda bir nechta variant bo’ldi — demak to’g’ri tartib bitta emas. Endi ataylab halqa qo’shing (masalan «kamar shimdan oldin»): birortasiga ham strelka kirmaydigan narsa qolmaydi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Kiruvchi daraja

“Kiruvchi daraja” bo'limiga havola
yo'naltirilgan grafdirected graph

Qirralari bir tomonlama bo’lgan graf: a dan b ga o’tish mumkin, teskarisi esa shart emas.

kiruvchi darajain-degree

Uchga kirayotgan strelkalar soni. Nol bo’lsa, undan oldin bajarilishi kerak bo’lgan hech narsa qolmagan.

Algoritm shu ikki tushunchadan chiqadi. Kiruvchi darajasi nol bo’lgan uchni olamiz, ro’yxatga yozamiz va uning keyingilarining darajasini bittaga kamaytiramiz. Yangi nollar paydo bo’ladi.

Sekin yechim

“Sekin yechim” bo'limiga havola

Har qadamda eng kichik nol darajali uchni qidiramiz: ro’yxatni boshidan oxirigacha ko’rib chiqamiz.

sekin.py
n = 5qirralar = [(1, 3), (2, 3), (3, 5), (4, 5)]keyingi = [[] for _ in range(n + 1)]daraja = [0] * (n + 1)for a, b in qirralar:  keyingi[a].append(b)  daraja[b] += 1olingan = [False] * (n + 1)tartib = []for _ in range(n):  tanlangan = -1  for k in range(1, n + 1):      if not olingan[k] and daraja[k] == 0:          tanlangan = k          break  if tanlangan == -1:      break  olingan[tanlangan] = True  tartib.append(tanlangan)  for v in keyingi[tanlangan]:      daraja[v] -= 1print(tartib if len(tartib) == n else "IMKONSIZ")

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

Bashorat qiling
n = 5qirralar = [(1, 3), (2, 3), (3, 5), (4, 5)]keyingi = [[] for _ in range(n + 1)]daraja = [0] * (n + 1)for a, b in qirralar:  keyingi[a].append(b)  daraja[b] += 1olingan = [False] * (n + 1)tartib = []for _ in range(n):  tanlangan = -1  for k in range(1, n + 1):      if not olingan[k] and daraja[k] == 0:          tanlangan = k          break  if tanlangan == -1:      break  olingan[tanlangan] = True  tartib.append(tanlangan)  for v in keyingi[tanlangan]:      daraja[v] -= 1print(tartib if len(tartib) == n else "IMKONSIZ")
Javobni ko'rish
[1, 2, 3, 4, 5]

Boshida 1, 2 va 4 ning darajasi nol. Eng kichigi — 1. Keyin 2 olinadi va 3 ning darajasi nolga tushadi.

Nega sekin

“Nega sekin” bo'limiga havola

Har qadamda butun ro’yxat qidiriladi: n qadam × n tekshiruv. Kurslar soni 100000 bo’lishi mumkin.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechimn = 1 000n = 100 000
Har qadamda qidirishn^210⁶sig‘adi10¹⁰sig‘maydi
Uyum bilann log n9 966sig‘adi10⁶sig‘adi

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

Tez yechim

“Tez yechim” bo'limiga havola

Nol darajali uchlarni uyumda saqlaymiz. heappop eng kichigini qidirmasdan beradi.

tez.py
import heapqn = 5qirralar = [(1, 3), (2, 3), (3, 5), (4, 5)]keyingi = [[] for _ in range(n + 1)]daraja = [0] * (n + 1)for a, b in qirralar:  keyingi[a].append(b)  daraja[b] += 1uyum = [k for k in range(1, n + 1) if daraja[k] == 0]heapq.heapify(uyum)tartib = []while uyum:  k = heapq.heappop(uyum)  tartib.append(k)  for v in keyingi[k]:      daraja[v] -= 1      if daraja[v] == 0:          heapq.heappush(uyum, v)print(tartib if len(tartib) == n else "IMKONSIZ")

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

Bashorat qiling
import heapqn = 5qirralar = [(1, 3), (2, 3), (3, 5), (4, 5)]keyingi = [[] for _ in range(n + 1)]daraja = [0] * (n + 1)for a, b in qirralar:  keyingi[a].append(b)  daraja[b] += 1uyum = [k for k in range(1, n + 1) if daraja[k] == 0]heapq.heapify(uyum)tartib = []while uyum:  k = heapq.heappop(uyum)  tartib.append(k)  for v in keyingi[k]:      daraja[v] -= 1      if daraja[v] == 0:          heapq.heappush(uyum, v)print(tartib if len(tartib) == n else "IMKONSIZ")
Javobni ko'rish
[1, 2, 3, 4, 5]

Har uch uyumga bir marta kiradi va bir marta chiqadi, har qirra bir marta ishlanadi. Uyum amallari log n turadi.

Sikl bo’lsa

“Sikl bo’lsa” bo'limiga havola

Halqa ichidagi uchlarning darajasi hech qachon nolga tushmaydi: har biri boshqasini kutadi. Shuning uchun ular umuman uyumga tushmaydi.

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

Bashorat qiling
import heapqn = 3qirralar = [(1, 2), (2, 3), (3, 1)]keyingi = [[] for _ in range(n + 1)]daraja = [0] * (n + 1)for a, b in qirralar:  keyingi[a].append(b)  daraja[b] += 1uyum = [k for k in range(1, n + 1) if daraja[k] == 0]heapq.heapify(uyum)tartib = []while uyum:  k = heapq.heappop(uyum)  tartib.append(k)  for v in keyingi[k]:      daraja[v] -= 1      if daraja[v] == 0:          heapq.heappush(uyum, v)print(tartib if len(tartib) == n else "IMKONSIZ")
Javobni ko'rish
IMKONSIZ

Uyum boshidanoq bo'sh: uchala uchning ham darajasi bir. Sikl aniqlashning butun usuli shu — tartibga hamma uch tushmasa, halqa bor.

Sinab ko’r

“Sinab ko’r” bo'limiga havola

Vizualda uch ustidagi son — kiruvchi daraja. Nolga tushgan uch tanlovga tayyor bo’lishini kuzating.

Topologik saralash

Uch ustidagi son — kiruvchi daraja. Nolga tushgan uch tanlovga tayyor.

Kiruvchi darajasi nol bo'lgan uchlar navbat bilan olinadi va ularning keyingilarining darajasi kamaytiriladi.

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

  1. Har uch ustidagi son — undan OLDIN kelishi kerak bo'lgan uchlar soni. Nol bo'lgan uchni hozir olish mumkin.
  2. Nol darajali uchlardan eng kichigi — 1. Uni tartibga qo'shamiz: 1.
  3. 1 olingach, 3 uchining darajasi bittaga kamaydi. Hali hech biri nolga tushmadi.
  4. Nol darajali uchlardan eng kichigi — 2. Uni tartibga qo'shamiz: 1 2.
  5. 2 olingach, 3 uchining darajasi bittaga kamaydi. 3 nolga tushdi — endi tanlovga tayyor.
  6. Nol darajali uchlardan eng kichigi — 3. Uni tartibga qo'shamiz: 1 2 3.
  7. 3 olingach, 5 uchining darajasi bittaga kamaydi. Hali hech biri nolga tushmadi.
  8. Nol darajali uchlardan eng kichigi — 4. Uni tartibga qo'shamiz: 1 2 3 4.
  9. 4 olingach, 5 uchining darajasi bittaga kamaydi. 5 nolga tushdi — endi tanlovga tayyor.
  10. Nol darajali uchlardan eng kichigi — 5. Uni tartibga qo'shamiz: 1 2 3 4 5.
  11. 5 olingach, 6 uchining darajasi bittaga kamaydi. 6 nolga tushdi — endi tanlovga tayyor.
  12. Nol darajali uchlardan eng kichigi — 6. Uni tartibga qo'shamiz: 1 2 3 4 5 6.
  13. Tartib: 1 2 3 4 5 6. Barcha 6 uch chiqdi, demak grafda sikl yo'q. Sikl bo'lganda esa hech qachon nolga tushmaydigan uchlar qolib ketardi.
123456

Har uch ustidagi son — undan OLDIN kelishi kerak bo'lgan uchlar soni. Nol bo'lgan uchni hozir olish mumkin.

Olingan uch0

1/13

Xatoni toping

“Xatoni toping” bo'limiga havola

Tuzoq — xatoni toping

22 / 40

MasalaKurslar tartibini toping, mumkin bo'lmasa IMKONSIZ deb yozing.

Taklif qilingan yechim

Bu javobning 4-qismi noto'g'ri. Uyum bo'shashi tartib tayyorligini bildirmaydi. Grafda sikl bo'lsa, halqa ichidagi uchlar hech qachon nolga tushmaydi va uyumga umuman tushmaydi — uyum bo'shaydi, tartib esa chala qoladi. Chiqarishdan oldin tartib uzunligini n bilan solishtirish shart.

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

O’zingizni sinang

“O’zingizni sinang” bo'limiga havola

1Kiruvchi daraja nima?

Javobni ko'rish

Uchga kirayotgan strelkalar soni. Nol bo’lsa, undan oldin bajarilishi kerak bo’lgan hech narsa qolmagan.

2Nega odatda «eng kichik tartib» so'raladi?

Javobni ko'rish

To’g’ri tartib bir nechta bo’lishi mumkin, tekshiruvchi esa bitta javobni kutadi. Eng kichigini talab qilish javobni yagona qiladi.

3Sikl borligini qanday aniqlaysiz?

Javobni ko'rish

Tartibga n ta uch tushmasa. Halqa ichidagi uchlarning darajasi hech qachon nolga tushmaydi, chunki ular bir-birini kutadi.

4Uyum o'rniga oddiy navbat ishlatilsa nima o'zgaradi?

Javobni ko'rish

Yechim baribir to’g’ri tartib beradi va tezroq ishlaydi (O(n + m)). Lekin u eng kichik tartibni kafolatlamaydi — shart shuni talab qilsa, uyum kerak.

5Topologik saralash qanday grafda mumkin?

Javobni ko'rish

Faqat sikli yo’q yo’naltirilgan grafda. Sikl bo’lsa tartib mavjud emas: halqadagi har uch o’zidan oldin turishi kerak bo’lib qoladi.

Masalalar

“Masalalar” bo'limiga havola

Masalalar

3 ta

  • Course ScheduleCSES 1679o'rta

    Darsdagi masalaning o‘zi. Bu yerda istalgan to‘g‘ri tartib qabul qilinadi.

  • Longest Flight RouteCSES 1680qiyin

    Topologik tartibda yuring va har uch uchun eng uzun yo‘lni oldingilardan yig‘ing.

  • Fox And NamesCodeforces 510Cqiyin

    Qo‘shni ikki so‘zdan bitta harf tartibi kelib chiqadi. Prefiks holatini alohida tekshiring.

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

Topshiriq

“Topshiriq” bo'limiga havola

Topshiriq — darajangizni tanlang

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

Ertalabki kiyinish grafingizni oling va barcha to’g’ri tartiblarni qog’ozda sanang. Nechta chiqdi? Endi bitta strelka qo’shib halqa yasang va nima o’zgarishini yozing.

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

22-tartib masalasini yeching. Generatoringiz siklli testlarni ham yasashini tekshiring — aks holda IMKONSIZ shoxi umuman sinalmagan bo’ladi.

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

Masalani kengaytiring: tartib nechta bo’lishini emas, tartib yagona ekanini aniqlang. Ishora: har qadamda uyumda bittadan ortiq uch bo’lsa, tanlov bor demakdir.

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