Concepts318
Category
Min-Cut Max-Flow Theorem
The Max-Flow Min-Cut Theorem says the maximum amount you can push from source to sink equals the minimum total capacity you must cut to disconnect them.
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.
Maximum Flow - Ford-Fulkerson
Ford–Fulkerson finds the maximum possible flow from a source to a sink by repeatedly pushing flow along an augmenting path in the residual graph.
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.
Strongly Connected Components
Strongly Connected Components (SCCs) partition a directed graph into maximal groups where every vertex can reach every other vertex in the group.
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.
Tarjan's SCC Algorithm
Tarjan’s algorithm finds all Strongly Connected Components (SCCs) of a directed graph in a single depth-first search using a stack.
Bridges and Articulation Points
A bridge is an edge whose removal increases the number of connected components; an articulation point is a vertex with the same property.
SPFA (Shortest Path Faster Algorithm)
SPFA is a queue-based optimization of Bellman–Ford that only relaxes edges from vertices whose distance just improved.