Algorithms

Algorithms for solving ACM/ICPC problems. Instead of writing some templates, which may not be easy to understand, they are used to solve some concrete problems. For some data structures and algorithms (like quick sort and red-black tree), there are some really efficient implements (like STL), I will just put them down to remind me how they work. Some simple structures like stack and queue will not be included.

Content

• utility
  • sort
    • quick sort
    • heap sort
    • merge sort
    • insert sort
    • select sort
    • bubble sort
    • shell sort
  • prime
  • big integer
  • union set
  • ST for RMQ
  • leftist heap
  • Fibonacci heap
• tree
  • AVL tree
  • splay tree
  • segment tree
  • binary indexed tree
  • LCA problem
  • red-black tree (hard to implement, pending...)
• graph
  • BFS / DFS
  • single source shortest path
    • Dijkstra (non-negative weights)
    • Bellman-Ford / SPFA (negative weights)
  • maximum flow
    • SAP
    • Dinic
    • Ford-Fulkerson
  • minimum spanning tree
    • Kruskal (sparse)
    • Prim (dense)
  • maximal matching (Hungary)
  • topology sort
  • Tarjan
• string
  • matching
    • KMP
    • Sunday
  • Levenshtein distance
  • Manacher
  • AC automation