Concepts80
Knapsack Problems
Knapsack problems ask how to pick items under a weight (or cost) limit to maximize value or to check if a target sum is reachable.
Coin Change and Variants
Coin Change uses dynamic programming to find either the minimum number of coins to reach a target or the number of ways to reach it.
Bipartite Matching - Hopcroft-Karp
Hopcroft–Karp computes maximum matching in a bipartite graph in O(E \sqrt{V}) time, which is asymptotically faster than repeated DFS (Kuhn's algorithm).
General Matching - Blossom Algorithm
Edmonds' Blossom Algorithm finds a maximum matching in any undirected graph, not just bipartite ones.
Bipartite Matching - Kuhn's Algorithm
Kuhn’s algorithm finds a maximum matching in a bipartite graph by repeatedly searching for augmenting paths using DFS.
König's Theorem
König's Theorem states that in any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
Maximum Flow - Dinic's Algorithm
Dinic's algorithm computes maximum flow by repeatedly building a level graph with BFS and sending a blocking flow using DFS.
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.
LCA - Binary Lifting
Binary lifting precomputes 2^k ancestors for every node so we can jump upward in powers of two.
Bridge Tree
A bridge tree is built by contracting every 2-edge-connected component of an undirected graph into a single node, leaving only bridges as edges between nodes.
Tree Distances and Diameter
Tree diameter is the longest simple path in a tree and can be found with two BFS/DFS runs.