Graph¶

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

Headers¶

Header	Summary
`best_theorem.hpp`	有向欧拉回路计数
`bipartite_decomposition.hpp`	匹配、覆盖、链与反链
`bipartite_edge_coloring.hpp`	二分多重图最优边染色
`bipartite_matching.hpp`	二分图最大匹配
`bipolar_orientation.hpp`	源汇约束的 st 顶点序
`block_cut_tree.hpp`	点双分量与圆方树
`centroid_decomposition.hpp`	点分治与路径统计
`chordal_graph.hpp`	弦图判定与证据
`chromatic_number.hpp`	精确最小顶点着色
`chromatic_polynomial.hpp`	合法着色数的多项式
`clique_enumeration.hpp`	所有非空团的权积之和
`complement_graph_components.hpp`	补图连通分量
`count_c4.hpp`	每条边参与的四元环数
`cycle.hpp`	判环、找环与拓扑排序
`directed_mst.hpp`	最小树形图
`dominator_tree.hpp`	支配树与必经点
`dsu_on_tree.hpp`	树上启发式合并
`dynamic_rerooting_top_tree.hpp`	动态森林换根与子树 DP
`dynamic_star_min_cut.hpp`	星形边权修改与全局最小割
`dynamic_tree_path_affine_sum.hpp`	全根路径仿射复合和
`dynamic_tree_subtree.hpp`	动态森林子树加与求和
`euler_walk.hpp`	有向与无向欧拉迹
`eulerian_trail.hpp`	欧拉迹顶点与边序列
`general_matching.hpp`	一般图最大基数匹配
`general_weighted_matching.hpp`	一般图最大权匹配
`global_min_cut.hpp`	无向图全局最小割
`gomory_hu_tree.hpp`	任意两点最小割树
`heavy_light_decomposition.hpp`	树链剖分与路径跳点
`hungarian.hpp`	矩形指派最小或最大费用
`incremental_msf.hpp`	增边维护最小生成森林
`incremental_scc.hpp`	增边强连通变化
`johnson.hpp`	含负边稀疏图全源最短路
`k_shortest_walk.hpp`	允许重复点边的前 k 短路
`lower_bound_flow.hpp`	上下界可行流与最大流
`lowest_common_ancestor.hpp`	最近公共祖先与树上距离
`lowlink.hpp`	割点、桥与双连通分量
`manhattan_mst.hpp`	曼哈顿最小生成树
`matrix_tree.hpp`	有向与无向生成树计数
`maximum_clique.hpp`	最大团与方案
`maximum_weight_closure.hpp`	带依赖选择的最大收益
`min_cost_b_flow.hpp`	带点供需与上下界的费用流
`minimum_diameter_spanning_tree.hpp`	最小直径生成树
`minimum_mean_cycle.hpp`	最小平均权环
`minimum_spanning_tree.hpp`	最小生成森林
`offline_dynamic_component_sum.hpp`	离线动态连通块权值和
`offline_dynamic_connectivity.hpp`	离线加删边与连通性
`prufer_code.hpp`	有标号树与 Prüfer 序列互转
`rerooting_dp.hpp`	全根树形 DP
`rooted_tree_isomorphism.hpp`	有根树同构分类
`rooted_tree_minimum_inversion_order.hpp`	祖先约束下最少逆序对
`shortest_path.hpp`	单源最短路与路径恢复
`small_cycle_count.hpp`	三角形与小环计数
`special_spanning_trees.hpp`	双权乘积最小生成树与切比雪夫 MST
`steiner_tree.hpp`	少量终端的最小连接代价
`strongly_connected_components.hpp`	有向图的强连通分量
`three_edge_connected_components.hpp`	三边连通分量
`tree_contour.hpp`	树上距离区间修改与查询
`tree_decomposition_width_two.hpp`	宽度二树分解
`tree_diameter.hpp`	树直径与路径恢复
`tree_distance_frequency.hpp`	树上所有点对距离分布
`tree_enumeration.hpp`	枚举有标号树或无标号树形
`tree_path_affine_sum.hpp`	静态全根路径仿射复合和
`tree_preprocessing.hpp`	父亲、深度与子树区间
`two_sat.hpp`	二元布尔约束求解
`undirected_girth.hpp`	无向图最短环
`virtual_tree.hpp`	关键点虚树