Concepts113
Category
General Matching - Blossom Algorithm
Edmonds' Blossom Algorithm finds a maximum matching in any undirected graph, not just bipartite ones.
Minimum Cost Maximum Flow
Minimum Cost Maximum Flow (MCMF) finds the maximum possible flow from a source to a sink while minimizing the total cost paid per unit of flow along edges.
Biconnected Components
A biconnected component (block) is a maximal subgraph where removing any single vertex keeps it connected.
Virtual Tree (Auxiliary Tree)
A Virtual Tree (Auxiliary Tree) compresses a large tree into a much smaller tree that contains only the k important nodes and the LCAs needed to keep them connected.
Johnson's Algorithm
Johnson's Algorithm computes all-pairs shortest paths on sparse graphs by first removing negative edges via reweighting, then running Dijkstra from every vertex.
Kinetic Tournament Tree
A kinetic tournament tree maintains the minimum (or maximum) of moving values whose pairwise order can change over time.
Aho-Corasick - DP Applications
Aho–Corasick (AC) turns a set of forbidden patterns into a finite automaton that lets you process or generate strings while tracking whether any pattern appears.
Li Chao Tree
A Li Chao tree maintains a set of lines y = m x + b and answers minimum (or maximum) value queries at a given x in O(log C) time, where C is the numeric range of x.
Palindromic Tree (Eertree)
A Palindromic Tree (Eertree) stores every distinct palindromic substring of a string as a node and can be built online in linear time.
Suffix Automaton - Advanced Usage
A suffix automaton (SAM) is a compact DFA that captures all distinct substrings of a string and supports many advanced queries in linear time.
Suffix Automaton
A suffix automaton (SAM) is the minimal deterministic finite automaton that recognizes all substrings of a string, built online in O(n) time and space.
Aho-Corasick Automaton
Aho–Corasick is a trie with failure links that finds all occurrences of many patterns in a single pass over the text.