Top 10 Algorithms and Data Structures for Competitive Programming
#Graph Algorithms
Breadth First Search (BFS)Depth First Search (DFS)Shortest Path from source to all vertices DijkstraShortest Path from every vertex to every other vertex Floyd WarshallMinimum Spanning tree PrimMinimum Spanning tree KruskalTopological Sort- Johnson’s algorithm - P
- Articulation Points (or Cut Vertices) in a Graph
- Bridges in a graph
#Dynamic Programming
Longest Common SubsequenceLongest Increasing SubsequenceEdit DistanceMinimum PartitionWays to Cover a Distance- Longest Path In Matrix
- Subset Sum Problem
- Optimal Strategy for a Game
- 0-1 Knapsack Problem
- Assembly Line Scheduling
#Searching And Sorting
Binary SearchQuick SortMerge Sort- Order Statistics
- KMP algorithm
- Rabin karp
- Z’s algorithm
- Aho Corasick String Matching
Counting Sort- Manacher’s algorithm: Part 1, Part 2 and Part 3
#Prime Numbers and Prime Factorization
Primality TestSet 1 (Introduction and School Method)Set 2 (Fermat Method)Set 3 (Miller–Rabin)Sieve of EratosthenesSegmented Sieve- Wilson’s Theorem - P
Prime FactorisationPollard’s rho algorithm
#Modulo Arithmetic Algorithms
Basic and Extended Euclidean algorithmsEuler’s Totient FunctionModular ExponentiationModular Multiplicative InverseChinese remainder theorem and Modulo Inverse ImplementationnCr%m
#Mathematical Algorithms
Counting InversionsCounting Inversions using BITlogarithmic exponentiationSquare root of an integer- Heavy light Decomposition and this
Matrix Rank- Hungarian algorithm
- Link cut
- Mo’s algorithm and this
Russian Peasant MultiplicationCatalan Number
#Geometrical and Network Flow Algorithms
- Convex Hull
- Graham Scan
- Line Intersection
- Interval Tree
- Matrix Exponentiation
- Maxflow Ford Furkerson Algo and Edmond Karp Implementation
- Min cut
- Stable Marriage Problem
- Hopcroft–Karp Algorithm for Maximum Matching
- Dinic’s algo
#Data Structures
- Binary Indexed Tree or Fenwick tree
- Segment Tree (RMQ, Range Sum and Lazy Propagation)
- K-D tree (See insert, minimum and delete)
- Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)
Tries- Suffix array (this, this and this)
- Sparse table
- Suffix automata
- Suffix automata II
- LCA and RMQ
Source @ https://www.geeksforgeeks.org/top-algorithms-and-data-structures-for-competitive-programming/