Concepts9

Rerooting (a.k.a. 换根 DP) computes a per-node answer as if each node were the root, in total O(n) time on trees.

A Block-Cut Tree decomposes an undirected graph into biconnected components (blocks) and articulation points, forming a bipartite tree.

Dinic's algorithm computes maximum flow by repeatedly building a level graph with BFS and sending a blocking flow using DFS.

A biconnected component (block) is a maximal subgraph where removing any single vertex keeps it connected.

Tree diameter is the longest simple path in a tree and can be found with two BFS/DFS runs.

A bridge is an edge whose removal increases the number of connected components; an articulation point is a vertex with the same property.

Depth-First Search (DFS) assigns each vertex a discovery time and a finish time that capture a neat nesting structure of recursion.

Depth-First Search (DFS) explores a graph by going as deep as possible along each path before backtracking.

Complete search enumerates every candidate solution, while backtracking prunes branches that cannot possibly lead to a valid or better solution.