4. Graph Algorithms | Các thuật toán trên đồ thị là một chủ đề được ứng dụng rộng rãi cả trong lập trình thi đấu và đời sống. Qua các bài tập này, các bạn sẽ học được cách giải quyết các vấn đề bằng cách biểu diễn chúng thành mạng lưới và sử dụng các thuật toán trên đồ thị để xử lý. Contest bao gồm các thuật toán và kiến thức sau:

• Duyệt đồ thị bằng DFS/BFS
• Tìm thành phần liên thông
• Tìm đường đi ngắn nhất (BFS, Dijkstra, Floyd-Warshall, Bellman-Ford/SPFA)
• Kiểm tra đồ thị hai phía
• Tìm chu trình đơn
• Tìm chu trình âm (Bellman-Ford/SPFA)
• Dựng DAG từ thuật toán Dijkstra
• Tìm thành phần liên thông mạnh (Tarjan)
• Topo Sort
• Quy hoạch động trên DAG
• Đồ thị hàm số
• Disjoint Set Union (DSU)
• 2-SAT
• Chu trình Euler, đường đi Euler
• Đường đi Hamilton
• Luồng:
  • Tìm luồng cực đại
  • Tìm lát cắt hẹp nhất
  • Tìm bộ ghép cực đại trên đồ thị hai phía

Hy vọng các bạn có thể tiếp thu được thêm nhiều kiến thức qua contest này.