מבוא

ברוכים השבים לסדרת אלגוריתמים על גרפים! הפעם נעבוד עם גרף מכוון, שבו לכל קשת יש כיוון: קשת u -> v פירושה ש-u חייב להופיע לפני v.

מיון טופולוגי מסדר את הקודקודים של גרף מכוון חסר מעגלים (DAG) בשורה, כך שכל קשת מצביעה קדימה. הוא עונה על שאלות כמו "באיזה סדר אפשר לקחת קורסים, בהתחשב בדרישות הקדם שלהם?"

הגרף נתון באמצעות n (הקודקודים 0 עד n - 1) ו-edges, מערך שטוח של זוגות מכוונים [u0, v0, u1, v1, ...], כאשר כל זוג פירושו u -> v.

בואו נתחיל!