Module DAG / Topological sort

DAG / Topological sort

**Frequency: 5/10** A Directed Acyclic Graph (DAG) is a graph that contains directed edges and does not have any cycles. Topological sorting is an algorithmic process used to order the vertices of a DAG in a linear sequence, where each vertex comes before its successors in the ordering. This algorithm is pivotal when it comes to problems relating to directed graph.

Resources

- [USACO: Topological Sort](https://usaco.guide/gold/toposort?lang=cpp) - [CP Algorithms: Topological Sorting](https://cp-algorithms.com/graph/topological-sort.html)

Problems

DAG 122 / 129 1200
Reading order 138 / 146 1300
Longest path 134 / 146 1400
Maximum path 97 / 105 1400
Martian language 80 / 83 1600
Edge direction 64 / 65 1700
Train pass 46 / 48 1900