report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
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 490 / 505 1200
Reading order 513 / 530 1300
Longest path 470 / 507 1400
Maximum path 349 / 375 1400
Martian language 277 / 295 1600
Edge direction 221 / 222 1700
Train pass 164 / 186 1900

Graph

  • Shortest path
  • 0-1 BFS / Dial's algorithm
  • Multisource BFS / Dijkstra
  • DAG / Topological sort

Data structure

  • Introduction to Segment Tree and Binary Indexed Tree
  • Sparse table
  • Monotonic queue

Tree

  • Lowest common ancestor (LCA)
  • Euler tour

Dynamic Programming

  • Bitmask DP
  • Exchange labels DP
  • Game DP

Math

  • Introduction to combinatorics
  • Inclusion-exclusion principle