C++ implementations of algorithms

1. Template

• Template for competitive programming
• Template for algorithm
• Template for marathon

2. Graph

• Bipartite maximum matching
• Lexicographic breadth first search
• Prüfer sequence
• Maximum independent set problem (using branch and reduce): O*(1.4423) time
• Hamiltonian path problem in hypercube graph

Recognition Problem

• Recognition of bipartite graph
• Recognition of chordal graph
• Recognition of cactus
• Eulerian graph by Hierholzer
• Eulerian digraph by Hierholzer

Graph Isomorphism Problem

• Tree isomorphism

Shortest Paths Problem

Single Source Shortest Paths Problem

• Dijkstra's algorithm: only distance
• Dijkstra's algorithm with heap: only distance
• Dijkstra's algorithm with heap: distance and path
• Bellman-Ford algorithm: only distance and check for negative cycles
• 0-1 BFS algorithm in a binary weighted digraph

All Pairs Shortest Paths Problem

• Floyd-Warshall algorithm: only distance

Connected Components

• Strongly connected components by Kosaraju
• 2-edge connected components (enumerating all bridges) by Hopcroft and Tarjan
• 2-vertex connected components (enumerating all articulation points)

Tree Problems

• Lowest common ancestor by doubling
• Lowest common ancestor by euler tour
• Diameter of a tree

Maximum Flow Problem

• Ford-Fulkerson algorithm
• Dinic's algorithm
• Maximum flow with lower bounds problem

Random Graph Generator

• Erdos-Renyi random graph

Uniform Spanning Tree

• Aldous's algorithm
• Wilson's algorithm

Random Labelled Tree

• Aldous's algorithm
• Prüfer sequence
• Wilson's algorithm

3. Data Structure

• Fenwick tree (add a single element / accumulate a prefix)
• Segment tree (update a single element / accumulate an interval)
• Union find
• Initializable array by Bentley

Query Problems Using Data Structure

Range Sum Query

• Fenwick tree

Range Minimum Query and Range Maximum Query

• Sparse table (preprocessing : O(n log n) time, query: O(1) time)

4. Number Theory

• Basic modular arithmetics
• Binomial coefficient modulo prime (memorization)
• Binomial coefficient modulo prime (naive method)
• GCD (greatest common divisor) and LCM (least common multiple)
• Generate primes at compile time
• Extended Euclid's Algorithm
• Prime factorization - Trial division

5. Numerical Analysis

• Gaussian elimination with pivoting

6. Approximation Algorithms

• Vertex cover problem (using maximal matching): 2-approximation algorithm

7. Other

• Counting sort
• 0-1 Knapsack problem (branch and bound method)
• 2-satisfiability problem
• Longest increasing subsequence problem

Pseudorandom Number Generator

• XorShift128 plus by Blackman and Vigna

8. Comparing speed in C++

• Is it true that std::vector<bool> is slow? (only flag usage)

9. 2D Geometry

• 2d geometry (this is not arranged. Let's use CGAL)

TODO Lists

• Strongly connected components by Tarjan
• Max cut prolbme on planar graph by F. Hadlock (1975)
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees