يمكن وصف الخوارزمية على النحو التالي:
إعطاء رسم بياني موجه برؤوس n وحواف m. مطلوب إعادة ترقيم رؤوسها بطريقة تؤدي بها كل حافة من قمة ذات رقم أقل إلى قمة ذات رأس أعلى.
بعبارة أخرى ، مطلوب إيجاد تبديل للرؤوس (ترتيب طوبولوجي) يتوافق مع الترتيب الذي تقدمه جميع حواف الرسم البياني.
سنستخدم بحث العمق أولاً (dfs (v))
إذا أضفنا رأسنا إلى بداية القائمة وقت الخروج من & nbsp؛
\ (dfs (v) \) & nbsp ؛، ثم في النهاية في هذه القائمة تحصل على تصنيف طوبولوجي.
وهكذا ، النوع الطوبولوجي المطلوب & [مدش] ؛ يتم ترتيب ذلك بترتيب تنازلي لأوقات الخروج.
Problem
بالنظر إلى رسم بياني موجه غير مرجح. & nbsp ؛ من الضروري فرزها طوبولوجيًا.
الإدخال: & nbsp؛ يحتوي السطر الأول على عددين طبيعيين n و m (1 & le؛ n & le؛ 10
5 ، 1 & le؛ m & le؛ 10
5 ) & [مدش] ؛ عدد الرؤوس والحواف في الرسم البياني ، على التوالي. تسرد سطور m التالية حواف الرسم البياني. يتم إعطاء كل حافة بواسطة زوج من الأرقام و [مدش] ؛ عدد رؤوس البداية والنهاية ، على التوالي.
& nbsp؛
الإخراج: & nbsp؛ اطبع أي نوع طوبولوجي للرسم البياني كسلسلة من أرقام الرؤوس. إذا تعذر ترتيب الرسم البياني طوبولوجيًا ، اطبع & ناقص؛ 1.
يحتوي السطر الأول على عدد الرؤوس N والحواف M. & nbsp؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
4 4
14
4 3
4 2
3 2 |
1 4 3 2 |