Graph

Tree techniques, graph decompositions, matching, and path algorithms.

Headers

Header	Summary
best_theorem.hpp	Count Euler circuits of an Eulerian directed multigraph by the BEST theorem. Delete the root row and column of the outgoing Laplacian to count in-arborescences rooted there, then multiply by (out_degree(v) - 1)! for every active vertex. This orders the remaining labeled outgoing edges after the arborescence chooses the last exit from each vertex. With fixed_first_edge=true, the first outgoing labeled edge at root is prescribed; otherwise all choices for that first edge are counted.
bipartite_decomposition.hpp	Hopcroft-Karp matching with Konig minimum vertex cover, maximum independent set, and a minimum edge cover when the graph has no isolates.
bipartite_edge_coloring.hpp	Color every edge of a bipartite multigraph with Delta colors so incident edges differ. Low-degree vertices are contracted before regularization, keeping the number of real and dummy edges linear.
bipartite_matching.hpp	Dense bipartite matching using bitset-accelerated augmenting paths.
bipolar_orientation.hpp	Find an st-numbering of a biconnected undirected graph with edge (source,sink), or return an empty vector if the graph is not suitable.
block_cut_tree.hpp	Block-cut incidence forest of an undirected multigraph. Original vertices use ids [0, n), and block nodes use ids [n, n + blocks.size()).
centroid_decomposition.hpp	Centroid-decomposition tree of an undirected tree.
chordal_graph.hpp	Chordality certificate: a perfect-elimination ordering, or an induced cycle of length at least four when the graph is not chordal.
chromatic_number.hpp	Exact minimum vertex coloring for an undirected graph with at most 64 vertices using DSATUR branch-and-bound.
chromatic_polynomial.hpp	Return the chromatic polynomial in ascending coefficient order. Mark every independent vertex subset by one in a set power series f. The full-set coefficient of f^k counts ordered partitions into k independent color classes, exactly the proper k-colorings. Power projection obtains these values for k=0,...,n simultaneously, and interpolation at those n+1 points recovers the degree-at-most-n chromatic polynomial. Self-loops make every containing subset dependent; parallel edges therefore need no special handling.
clique_enumeration.hpp	Sum the products of vertex weights over all nonempty cliques. Vertices are ordered by degree and every clique is generated exactly once from its smallest vertex in that order. Recursion intersects the remaining candidates with the chosen vertex's adjacency bitset, so only prefixes that are already cliques are visited.
complement_graph_components.hpp	Connected components of the complement of an undirected graph.
count_c4.hpp	Count, for every edge of an undirected multigraph, how many four-edge subsets containing it form a simple four-cycle. Parallel edges are first grouped into a weighted simple graph; the degree orientation then charges every length-two path to a low-degree middle vertex.
cycle.hpp	Topological ordering and cycle detection for directed and undirected graphs.
directed_mst.hpp	Minimum spanning arborescence rooted at root in O(m log n). Edges are (cost, from, to).
dominator_tree.hpp	Immediate dominators in a directed graph using Lengauer-Tarjan. The root dominates itself; unreachable vertices have parent -1.
dsu_on_tree.hpp	DSU on tree. add(u) adds vertex u, query(u, x) queries contribution of x to u, del(u) removes vertex u.
dynamic_rerooting_top_tree.hpp	Dynamic rerooting DP on a top tree represented by preferred paths. compress joins consecutive path clusters, while commutative rake combines light subtrees. add_edge changes a path cluster into a point cluster and add_vertex attaches all light clusters to one path vertex. Expose moves preferred edges between the path splay and the dashed-edge splay, so both forward and reversed path aggregates stay current.
dynamic_star_min_cut.hpp	Maintain the global min-cut after changing edges of an added star. Repeated minimum-adjacency pendant-pair contractions build a binary cluster tree with an optimal cut among its rooted clusters for every nonnegative star weighting. A cluster's cut is its original-graph boundary plus the star weights of its leaves. Thus a leaf update adds one value to all its ancestors; heavy-light path updates and a global-min segment tree maintain the best cluster cut.
dynamic_tree_path_affine_sum.hpp	Maintain sums of edge-affine transforms from any chosen root. Every original edge is split by an edge-node carrying its affine map. A top tree cluster stores the affine transform along its boundary path, the sum of all values entering that path, and their count. Compress composes paths; rake adds independent branches. Preferred-path expose therefore propagates a point update to the complete rerooted aggregate in logarithmic time.
dynamic_tree_subtree.hpp	Link-Cut Tree with dynamic-edge subtree additions and sums.
euler_walk.hpp	Find an Euler trail in an undirected multigraph, or nullopt if none exists.
eulerian_trail.hpp	Vertex sequence and input edge ids of an Eulerian trail.
general_matching.hpp	Maximum matching in a general undirected graph in O(n^3).
general_weighted_matching.hpp	Compute a maximum-weight matching in a general undirected graph. A primal-dual Edmonds search grows an alternating forest through zero reduced-cost edges. Odd cycles are contracted into blossoms; dual changes schedule grow, contract, and expand events. Gabow's heavy-blossom grouping and meldable heaps make all slack/event maintenance near-linear per search.
global_min_cut.hpp	Stoer-Wagner global minimum cut of an undirected weighted graph in O(n^3), returning (cut weight, one side of the cut).
gomory_hu_tree.hpp	Gomory-Hu tree representing every pairwise minimum cut of an undirected nonnegative-capacity graph.
heavy_light_decomposition.hpp	Heavy-light decomposition for path and subtree queries on trees.
hungarian.hpp	Hungarian algorithm.
incremental_msf.hpp	Maintain the unique minimum spanning forest under edge insertions. Represent every selected edge by an extra Link-Cut Tree vertex carrying (weight,id), while original vertices carry minus infinity. A cycle-forming insertion exposes its endpoint path: the heaviest selected edge is replaced exactly when it is heavier. Removed edge vertices are reused, so at most n-1 extra nodes are needed even for an arbitrarily long insertion stream.
incremental_scc.hpp	Return a certificate time for every edge in an incremental graph. Divide the prefix-time interval at its midpoint and compute SCCs using the edges already present there. Edges internal to one SCC recurse into the earlier half; all other edges recurse into the later half after contracting those SCCs. Thus every recursion level is linear in its active graph. An edge with returned time t joins its endpoint components after the first t insertions; applying all such joins reconstructs every SCC partition. edge_count+1 denotes an edge that never joins two distinct components.
johnson.hpp	Johnson all-pairs shortest paths for a sparse directed graph in O(nm + nm log n); nullopt means the graph contains a negative cycle.
k_shortest_walk.hpp	Return the lengths of the first k source-to-target directed walks. Reverse Dijkstra fixes one shortest-path tree toward the target. Every non-tree edge has a nonnegative sidetrack cost weight+dist[to]-dist[from]; a walk is its shortest base path plus an ordered sequence of sidetracks. Persistent leftist heaps collect all sidetracks available along each tree path. A final priority queue explores replacing a chosen sidetrack by a heap child or appending one after its destination, so walks are emitted in nondecreasing total length. Vertices and edges may repeat, including through zero-weight cycles.
lower_bound_flow.hpp	Feasible circulation and maximum flow with lower and upper edge bounds.
lowest_common_ancestor.hpp	Sparse-table-based LCA with O(n log n) build and O(1) query.
lowlink.hpp	Lowlink decomposition of an undirected multigraph.
manhattan_mst.hpp	Compute candidate edges for Manhattan MST in O(n log n).
matrix_tree.hpp	Count weighted spanning trees of an undirected graph over a field using the Matrix-Tree theorem in O(n^3) time.
maximum_clique.hpp	Return a maximum clique of an undirected graph with at most 64 vertices using branch-and-bound with greedy coloring.
maximum_weight_closure.hpp	Maximum-weight vertex set closed under implications (from selected implies to selected), using one s-t min cut.
min_cost_b_flow.hpp	Minimum- or maximum-cost feasible b-flow with lower and upper bounds. Lower bounds are represented as reverse residual capacity and vertex supplies are maintained as excesses. Capacity scaling repeatedly saturates negative reduced-cost residual edges, then a multi-source Dijkstra dual step updates potentials and a primal step routes one scaling unit from excess vertices to deficits. When the scale reaches one, residual reduced costs certify optimality; a remaining excess certifies infeasibility.
minimum_diameter_spanning_tree.hpp	Construct a minimum-diameter spanning tree of a connected graph. The center of an optimal tree can be placed at a vertex or inside one graph edge. All-pairs shortest paths give every vertex eccentricity. For an edge center, sorting vertices by distance from one endpoint makes the maximum of the two endpoint-distance envelopes change monotonically, so one sweep tests its best split point. Doubling edge weights keeps every half-integral center exact. Finally, a shortest-path tree rooted at the best absolute center realizes the selected minimum diameter.
minimum_mean_cycle.hpp	Minimum mean edge weight among directed cycles by Karp's O(nm) dynamic program; nullopt means the graph is acyclic.
minimum_spanning_tree.hpp	Kruskal's MST. Edges are (w, u, v).
offline_dynamic_component_sum.hpp	Offline fully dynamic undirected connectivity with additive vertex values and component-sum queries. Every edge and every vertex increment is placed on the segment-tree nodes covering the time interval where it is active. A depth-first traversal applies those operations to a union-find whose parent links and component sums can both be rolled back, so each leaf sees exactly the graph and values at that query time.
offline_dynamic_connectivity.hpp	Offline fully dynamic connectivity with add, remove, and same queries.
prufer_code.hpp	Encode a labeled tree on vertices [0, n) as its Prüfer sequence in O(n log n), always removing the smallest current leaf.
rerooting_dp.hpp	Generic rerooting DP on a tree. merge combines neighbor contributions, add_edge(value, from, to) moves a rooted value across an edge, and add_vertex(value, vertex) closes a vertex.
rooted_tree_isomorphism.hpp	Assign canonical hash labels to rooted subtrees for isomorphism testing.
rooted_tree_minimum_inversion_order.hpp	Find a parent-before-child order minimizing the weighted inversion cost. For two independent blocks A and B, placing A first contributes d(A)c(B), while placing B first contributes d(B)c(A); hence the better block order is decreasing c/d. Sidney's decomposition for an out-tree is obtained by repeatedly contracting the maximum-ratio non-root block into its parent block. A labeled DSU finds that current parent block, while a cyclic linked list records the corresponding concatenations. The returned cost is sum over i < j of d[order[i]] * c[order[j]]. All weights must be nonnegative, and Weight must hold aggregate sums and their products.
shortest_path.hpp	Shortest-path routines for unweighted, 0/1-weighted, nonnegative, and signed-weight graphs.
small_cycle_count.hpp	Count triangles in an undirected simple graph in O(m sqrt(m)) orientation time; duplicate input edges and self-loops are ignored.
special_spanning_trees.hpp	Find a spanning tree minimizing (sum first_weight)*(sum second_weight) by recursive supported-point search on the bicriteria spanning-tree hull.
steiner_tree.hpp	Construct a minimum Steiner tree in an undirected graph. Subset DP first joins two terminal groups at a common vertex, then a multi-source Dijkstra closure moves that root through the graph. Parent records replay both transitions and recover the selected original edge indices.
strongly_connected_components.hpp	Decompose a directed graph into strongly connected components in topological order.
three_edge_connected_components.hpp	Decompose an undirected multigraph into maximal vertex sets that remain mutually connected after deleting any two edges. The DFS maintains for each active subtree its earliest back-edge endpoint, the net number of upward paths, and a linked chain of unfinished pieces. Whenever a chain can no longer be separated by a cut of size at most two, its circular lists are spliced in O(1). Each vertex and edge enters and leaves a chain once.
tree_contour.hpp	Centroid-decomposition distance-range updates and queries on a static tree.
tree_decomposition_width_two.hpp	Recognize treewidth at most two and construct a decomposition. Repeatedly remove a live vertex of degree at most two; when it has two neighbors, add the missing edge between them. This reduction is exact: suppressing a degree-two vertex produces a minor, while a decomposition of the filled graph extends by attaching the bag {vertex, first, second}. Reversing the eliminations and attaching each new bag to a later bag that contains its surviving neighbor set yields bags of size at most three.
tree_diameter.hpp	Unweighted tree diameter via double BFS.
tree_distance_frequency.hpp	Count unordered vertex pairs at every distance in an unweighted tree. At each centroid, squaring the frequency vector of all depths counts every ordered path through that centroid; subtracting the square for each child component removes paths that do not pass through it. Centroid decomposition assigns every pair to one level. Two NTT-friendly moduli and CRT recover the exact integer counts, after which division by two removes pair orientation.
tree_path_affine_sum.hpp	Sum edge-affine path transforms from every possible root. For an oriented edge x-y, the message sent by y is the sum of path values whose destinations lie on y's side after deleting the edge. Applying bx+c to all of them gives b times that message plus c times the side size. One postorder pass builds child-side messages; one preorder reroot pass supplies the complementary parent-side message.
two_sat.hpp	Incremental 2-SAT formula. A clause is (x_i == first_value) OR (x_j == second_value).
undirected_girth.hpp	Return edge ids of a shortest cycle in an undirected multigraph, or an empty vector for a forest; self-loops and parallel-edge 2-cycles count.
virtual_tree.hpp	Vertices and parent edges of a compressed virtual tree.