टोपोलॉजिकल सॉर्टिंग
किसी निर्देशित ग्राफ़ (directed graph) में
v शीर्ष (vertices) और e धाराएँ (edges) हैं, जिनमें आप इन शीर्षों को एक विशिष्ट क्रम में व्यवस्थित करना चाहते हैं। यदि कोई धारा v1 से v2 की ओर जाती है, तो स्रोत शीर्ष v1 को v2 से पहले आरे (array) में आना चाहिए। यानी, शीर्षों को क्रमबद्ध करने के बाद प्रत्येक धारा एक छोटे इंडेक्स वाले शीर्ष से बड़े इंडेक्स वाले शीर्ष तक जानी चाहिए।🤔
ध्यान दें कि टोपोलॉजिकल सॉर्टिंग के कई वैध क्रम संभव हैं।
दूसरी ओर, यदि ग्राफ़ में चक्र (cycles) मौजूद हों, तो कोई भी वैध टोपोलॉजिकल सॉर्टिंग संभव नहीं है।
इस एल्गोरिथ्म को एक DFS (Depth First Search) से लागू किया जा सकता है, जो उन सभी शीर्षों से शुरू होता है जिन्हें अभी तक विज़िट (visited) नहीं किया गया है। प्रत्येक DFS चरण में, हम पहले पुनरावृत्त (recursively) ढंग से वर्तमान शीर्ष के सभी बाल (child) नोड्स जोड़ते हैं और उसके बाद ही, जब सारे बाल शीर्ष संसाधित हो जाते हैं, तब मौजूदा शीर्ष को उत्तर सूची (answer list) में डाल देते हैं। इससे यह सुनिश्चित होता है कि स्रोत शीर्ष उन सभी से बाद में जुड़ता है, जो उससे पहुँचे जा सकते हैं। एल्गोरिथ्म के अंत में, हम अंत में बनी उत्तर सूची को उलट (reverse) देते हैं:
used = [False] * n # उपयोग में लिए गए वर्टिस
order = [] # टोपोलॉजिकल क्रम
def dfs(v): # डीएफ़एस
used[v] = True # वर्टिस को उपयोगित चिह्नित करें
for to in g[v]: # v से जुड़े प्रत्येक वर्टिस के लिए
if not used[to]: # अगर to अभी उपयोग में नहीं लिया गया
dfs(to) # to से डीएफ़एस
order.append(v) # टोपोलॉजिकल क्रम में v जोड़ें
for i in range(n): # प्रत्येक वर्टिस के लिए
if not used[i]: # अगर वर्टिस अभी उपयोग में नहीं लिया गया
dfs(i) # वर्टिस से डीएफ़एस शुरू करें
print(*order[::-1]) # टोपोलॉजिकल क्रम को प्रिंट करेंचुनौती: कोर्स शेड्यूल व्यवस्थित करें
आपको
n पाठ्यक्रम (courses) दिए गए हैं, जिन्हें आप लेना चाहते हैं। इनके लिए कुल p पूर्वआवश्यकताएँ (prerequisites) हैं। प्रत्येक पूर्वआवश्यकता पाठ्यक्रमों के एक जोड़े को दर्शाती है, जिसका अर्थ है कि पाठ्यक्रम लेने से पहले आपको पाठ्यक्रम लेना होगा (यदि जोड़ा 1, 2 है, तो इसका मतलब कि पाठ्यक्रम 1 लेने से पहले पाठ्यक्रम 2 लेना अनिवार्य है)।आपको यह जाँचना है कि क्या सभी पाठ्यक्रम पूरे करना संभव है।
Input
इनपुट की पहली पंक्ति में दो पूर्णांक
n और p (1 ≤ n, p ≤ 10 000) होंगे।अगली
p पंक्तियों में प्रत्येक में दो पूर्णांक (1 ≤ ≤ n) होंगे।Output
यदि सभी पाठ्यक्रम लेना संभव हो, तो प्रोग्राम
Yes प्रिंट करे, अन्यथा No।Examples
इनपुट | आउटपुट |
2 1
2 1 | Yes |
2 2
2 1
1 2 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB