Hello Codeforces!↵
↵
### **What is Topological Sort?**↵
Topological Sort is an algorithm used to arrange nodes in a linear sequence. If there is a condition that node $u$ must be completed before node $v$, then $u$ must appear first in the ordering.↵
↵
To visualize it simply, think of it as a "prerequisite tree." For example, you cannot study a Data Structures (DS) course before you finish Introduction to Programming.↵
↵
**Time Complexity:**↵
$O(V + E)$↵
↵
---↵
↵
### Implementation in Python↵
↵
In Python, there is a handy built-in library called `graphlib` that does this sorting easily. All you have to do is pass it a Dictionary containing each subject and a List of the subjects that must be finished before it:↵
↵
```python↵
from graphlib import TopologicalSorter, CycleError↵
↵
# Dictionary containing each subject and its prerequisites↵
preds = {↵
1: [], # Subject 1 has no prerequisites↵
2: [1], # Subject 2 requires subject 1 to be finished first↵
3: [1, 2] # Subject 3 requires subjects 1 and 2↵
}↵
↵
ts = TopologicalSorter(preds)↵
↵
try:↵
order = list(ts.static_order())↵
print("Study Order:", *order) # Study Order: 1 2 3↵
except CycleError:↵
print("-1\n")↵
↵
```↵
↵
Happy coding!
↵
### **What is Topological Sort?**↵
Topological Sort is an algorithm used to arrange nodes in a linear sequence. If there is a condition that node $u$ must be completed before node $v$, then $u$ must appear first in the ordering.↵
↵
To visualize it simply, think of it as a "prerequisite tree." For example, you cannot study a Data Structures (DS) course before you finish Introduction to Programming.↵
↵
**Time Complexity:**↵
$O(V + E)$↵
↵
---↵
↵
### Implementation in Python↵
↵
In Python, there is a handy built-in library called `graphlib` that does this sorting easily. All you have to do is pass it a Dictionary containing each subject and a List of the subjects that must be finished before it:↵
↵
```python↵
from graphlib import TopologicalSorter, CycleError↵
↵
# Dictionary containing each subject and its prerequisites↵
preds = {↵
1: [], # Subject 1 has no prerequisites↵
2: [1], # Subject 2 requires subject 1 to be finished first↵
3: [1, 2] # Subject 3 requires subjects 1 and 2↵
}↵
↵
ts = TopologicalSorter(preds)↵
↵
try:↵
order = list(ts.static_order())↵
print("Study Order:", *order) # Study Order: 1 2 3↵
except CycleError:↵
print("-1\n")↵
↵
```↵
↵
Happy coding!
