Concepts18
Think Backwards (Reverse Thinking)
Think Backwards is a problem‑solving pattern where you reverse time or direction so hard deletions become easy insertions and the final state becomes the starting point.
Bidirectional BFS (Meet in the Middle Search)
Bidirectional BFS searches forward from the start and backward from the goal to meet in the middle, drastically reducing explored states.
Tree DP - Rerooting Technique
Rerooting (a.k.a. 换根 DP) computes a per-node answer as if each node were the root, in total O(n) time on trees.
DP on Trees
DP on trees is a technique that computes answers for each node by combining results from its children using a post-order DFS.
2-SAT
2-SAT solves Boolean formulas where every clause has exactly two literals, and it is solvable in linear time relative to the size of the implication graph.
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).
Bipartite Matching - Kuhn's Algorithm
Kuhn’s algorithm finds a maximum matching in a bipartite graph by repeatedly searching for augmenting paths 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.
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.
SPFA (Shortest Path Faster Algorithm)
SPFA is a queue-based optimization of Bellman–Ford that only relaxes edges from vertices whose distance just improved.
MST Properties and Applications
An MST minimizes total edge weight over all spanning trees and has powerful properties such as the cut and cycle properties that guide correct, greedy construction.
Minimum Spanning Tree - Prim
Prim's algorithm builds a Minimum Spanning Tree (MST) by growing a tree from an arbitrary start vertex, always adding the lightest edge that connects the tree to a new vertex.