Ажлуудыг «эхлээд энийг, дараа нь тэрийг» гэсэн дүрмүүдийг зөрчихгүй дарааллаар эрэмбэлдэг арга.

Advanced & LegendХугацаа: O(n + m)Санах ой: O(n + m)

Эхлээд жижиг бодлого

4 ажил байна. Edge-үүд: 1 → 2, 3 → 2, 2 → 4. Өөрөөр хэлбэл 2-ыг 1, 3-ын дараа, 4-ийг 2-ын дараа хийнэ.

in нь: 1-д 0, 2-т 2, 3-т 0, 4-т 1. Эхлээд 1, 3 Queue-д орно. 1-ийг аваход in[2] = 1, 3-ыг аваход in[2] = 0 болж 2 орно. 2-ыг аваход 4 орно. Хариу: 1 3 2 4.

Энгийн аргаас санаа руу

Энгийн арга: n ажлын бүх n! дарааллыг шалгаад, дүрэм зөрчөөгүйг нь олох. n = 10 бол 3.6 сая дараалал, n = 20 бол хэтэрхий олон.

Гол санаа: юуг ч хүлээгээгүй ажлыг одоо шууд хийж болно. Ийм ажил бол in = 0 node. Түүнийг эрэмбэнд нэмээд гарах edge-үүдийг нь арилгана. Тэгэхэд өөр node-уудын in багасч, шинэ in = 0 node гарч ирнэ. Энэ аргыг Kahn-ы алгоритм гэдэг.

Нэр томьёо ба тэмдэглэгээ

in[v]
v рүү орж ирдэг edge-ийн тоо, өөрөөр хэлбэл v-гийн хүлээж буй ажлын тоо.
q
in = 0 болсон боловч эрэмбэнд хараахан ороогүй node-уудын Queue.
order
Олдсон эрэмбэ.
DAG
Cycle-гүй чиглэлтэй graph. Зөвхөн DAG-д эрэмбэ олддог.
cycle
Бие биеэ тойрон хүлээсэн node-ууд: 3 → 4 → 5 → 3.
1in=22in=13in=04in=05in=26in=27in=1
q (Queue)
хоосон
order
хоосон

Ажлуудыг зөв дарааллаар эрэмбэлье. Edge 3 → 1 бол эхлээд 3, дараа нь 1. Node бүрийн доорх in нь тухайн node руу орж ирдэг edge-ийн тоо.

Алхам 1 / 23
Хурд
  • Одоогийн node / edge
  • Queue-д байгаа
  • in = 0 боллоо
  • Эрэмбэнд орсон
  • Cycle-д гацсан
Слайд 1 / 7

Юуг нь эхэлж хийх вэ?

Оймсоо өмсөөд дараа нь гутлаа өмсдөг шиг зарим ажил өөр ажлаас өмнө хийгдэх ёстой. Сум хэлбэртэй edge ийм дүрмийг заана.

topological-sort.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, in[105];
vector<int> g[105];
vector<int> order;
queue<int> q;
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
in[v]++;
}
for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
for (int i = 1; i <= n; i++) if (in[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) {
in[v]--;
if (in[v] == 0) {
q.push(v);
}
}
}
if ((int)order.size() < n) {
cout << -1 << '\n';
} else {
for (int u : order) cout << u << ' ';
}
return 0;
}

Юунд хэрэгтэй вэ?

Хичээлийн өмнөх нөхцөл, ажлын дараалал гэх мэт хамааралтай бодлогод зөв дарааллыг олно. Graph cycle-тай эсэхийг ч мэднэ.

Яаж ажилладаг вэ?

1. Node бүрийн in нь тухайн node руу орж ирдэг edge-ийн тоо. 2. in = 0 node-уудыг дугаарын дарааллаар нь Queue-д хийнэ. 3. Queue-гийн эхний node-ыг гаргаж эрэмбэнд нэмнэ. 4. Түүнээс гарах edge бүрийг арилгаж, edge-ийн төгсгөлийн in-ийг нэгээр багасгана. in = 0 болсон node Queue-гийн ард орно. 5. Бүх node эрэмбэнд орвол хэвлэнэ. Үгүй бол graph cycle-тай тул хариу -1. Оролт: эхний мөрөнд n ба m, дараа нь m мөрөнд «u v», өөрөөр хэлбэл u → v edge.

Яагаад зөв, хэр хурдан бэ?

Node эрэмбэнд орох үед түүний in = 0 байна. Энэ нь түүн рүү ирдэг бүх edge-ийн эхлэл аль хэдийн эрэмбэнд орсон гэсэн үг. Тиймээс edge бүрийн эхлэл төгсгөлөөсөө өмнө явна. Cycle байвал түүн дээрх node бүр cycle-ын өөр нэг node-ыг хүлээдэг. Тиймээс тэдний аль нь ч эхэлж in = 0 болж чадахгүй. order богино үлдэж, -1 гарна.

Node бүр Queue-д нэг удаа орж, edge бүр нэг удаа арилна: хугацаа O(n + m). n = 100 000, m = 200 000 бол 300 000 орчим үйлдэл.

Түгээмэл алдаа

  • Edge унших үед in[v]++ хийхээ мартах.
  • Cycle шалгахгүйгээр order-ыг хэвлэх. Эрэмбэ дутуу байж болно, order.size() < n эсэхийг шалга.
  • Бодлого толь бичгийн хамгийн бага эрэмбийг шаардсан үед энгийн Queue ашиглах. Тэр үед priority_queue<int, vector<int>, greater<int>> хэрэгтэй.
  • Edge-ийн чиглэлийг эсрэгээр нь унших. "u-г v-гээс өмнө" гэдэг нь u → v edge.

Хязгаарын тохиолдол

  • Edge огт байхгүй: бүх node эхэндээ in = 0, хариу 1 2 … n.
  • Нэг урт гинж: эрэмбэ ганцхан, гинжний дараалал.
  • Өөрөө өөр лүүгээ заасан edge (u → u): in нь хэзээ ч 0 болохгүй, хариу -1.
  • Хариу олон байж болно. Энэ код in = 0 node-уудыг дугаарын дарааллаар нь эхэлж Queue-д хийдэг.

Өөрийгөө шалга

  1. 1 → 2, 2 → 3, 3 → 1 graph дээр хариу юу вэ?

    Хариу харах

    -1. Гурвуулаа cycle дээр байгаа тул in = 0 node эхнээсээ алга.

  2. n = 4, edge-үүд 2 → 1, 4 → 3 бол хариу юу вэ?

    Хариу харах

    2 4 1 3. Эхлээд in = 0 байгаа 2, 4 Queue-д орно.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Animation-ы жишээн дээр Queue ба order хэрхэн өөрчлөгдөхийг бич: 3 → 1, 3 → 5, 4 → 5, 4 → 6, 5 → 1, 5 → 2, 5 → 7, 7 → 6.

    Hint харах

    Эхэндээ in = 0 нь 3, 4 хоёр.

    Хариу ба тайлбар

    3, 4 гарсны дараа 5 орно. 5 гарахад 1, 2, 7 орно. 7 гарахад 6 орно. Хариу 3 4 5 1 2 7 6.

  2. 2.Эрэмбэ олдоогүй үед cycle дээрх node-уудыг хэвлэ.

    Hint харах

    Kahn дууссаны дараа in > 0 үлдсэн node-уудыг хар.

    Хариу ба тайлбар

    for (int i = 1; i <= n; i++) if (in[i] > 0) хэвлэнэ. Эдгээр нь cycle дээр эсвэл cycle-аас хамааралтай node-ууд. Animation-ы cycle-тай жишээн дээр 3, 4, 5.

  3. 3.Улирал бүрт хүссэн хэдэн ч хичээл үзэж болно. Edge нь өмнөх нөхцөл. Бүх хичээлийг хамгийн цөөндөө хэдэн улиралд үзэх вэ?

    Hint харах

    level[v] = max(level[v], level[u] + 1) гэж edge бүрийг арилгах үед шинэчил.

    Хариу ба тайлбар

    in = 0 node-ууд level 1. Хариу нь хамгийн том level. Animation-ы жишээн дээр 3, 4 нь 1, 5 нь 2, 1, 2, 7 нь 3, 6 нь 4 тул 4 улирал.

Жишээ

Оролт

7 8
3 1
3 5
4 5
4 6
5 1
5 2
5 7
7 6

Гаралт

3 4 5 1 2 7 6