# template

**Repository Path**: wrz0318/template

## Basic Information

- **Project Name**: template
- **Description**: No description available
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-02-12
- **Last Updated**: 2022-07-22

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## Algorithm Templates

#### Data structures
* DSU
* Fenwick Tree
* 2D Fenwick Tree
* Fenwick Tree with RMQ
* Link Cut Tree
* Segment Tree
* Sparse Table
* Splay Tree
* Treap Tree

#### Flow
* Edmonds Blossom-Contraction Algorithm
  * *Solves maximum cardinality matchings*
  * *Time Complexity $\Theta(|V||E|^2)$*

* Dinic
* Flow graph
* Hungarian
  * ***Combinatorial optimization algorithm***
  * *Solves assignment problem*
  * *Time complexity $\Theta(n^3)$, strictly polynomial*

* Matching
  * *Solves bipartite graph maximum matching*


* Minimum Cost Maximum Flow

#### Graph

* Edge Biconnected Component
* Vertex Biconnected Component
* Bridges
* Cut Points
* Graph classes
  * Undirected graph
  * Directed graph
* Forest classes
  * DFS (initializes some useful vectors)
  * Lowests Common Ancestor
  * Heavy Light Decomposition
* Minimum Spanning Tree
* Strongly Connected Components
* 2-SAT
* Eulerian Path
* Dijkstra (heap version)
* Find cycles
* Topsort

#### Miscellaneous

* Fast Input & Output
* RNG

#### Number Theory

* Chinese Remainder Theorem Garner's Algorithm
* Extended GCD
* Fast Fourier Transform
* Gaussian Elimination
* Modular Integer
* Number Theroy Transform
* Polynomial

#### Strings

* Boyer Moore Algorithm
  * *Solves Pattern Matching*
  * *Worst Time Complexity $\Theta(NM)$*
  * *Best Time Complexity $\Theta\left(\frac{N}{M}\right)$*
* Manacher
  * *Finds palindromes with odd length, modify if needs even length palindromes*
  * *Linear Time Complexity*