tshita/algorithm

Some relative links on this page are broken. Please visit the README.md instead.

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

• 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 of bipartite graph
• Recognition of chordal graph
• Recognition of cactus
• Eulerian graph by Hierholzer
• Eulerian digraph by Hierholzer

• Tree isomorphism

• 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

• Floyd-Warshall algorithm: only distance

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

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

• Ford-Fulkerson method
• Edmonds-Karp algorithm
• Gabow's algorithm (capacity scaling algorithm)
• Dinic's algorithm
• Maximum flow with lower bounds problem

• Erdos-Renyi random graph

• Aldous's algorithm
• Wilson's algorithm

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

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

• Fenwick tree

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

• 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

• Gaussian elimination with pivoting

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

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

• Collection of problems in computational geometry solved in C++
  The geometry library move it because it is easier to organaize in a problem-driven way.
• 2D geometry (Let's use CGAL)

• Make N Ex.) Make$13$from$\lbrace 2, 5, 5, 9 \rbrace$☞$(9 - 5) \times 2 + 5$

• Kuwahara filter 　

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

• XorShift128 plus by Blackman and Vigna

• 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

These codes are licensed under CC0.