双连通分量（DCC）——Tarjan 原理 和 SCC 一样都是在 dfs 生成树上记录 dfn 和 low，在环中编号最小的。 需要做一下概念上的区分： SCC（强连通分量） 是针对有向图的概念。一个SCC内的任意两个节点都可以互相到达（即存在双向路径）。 DCC（双连通分量） 是针对无向图的概念
Heavy-Light Decoposition 重链剖分 什么是重链剖分？ 树链剖分 树链剖分是指，将一棵树分成若干条链，使得这些链具有某些性质，使得树上操作变为链上操作和跳链操作（链间操作）。 重链剖分（Heavy-Light Decomposition，简称 HLD）是一种把树分解为若干条链的
树的直径 定义 树的直径是指树中任意两个节点之间的最长路径的长度（边数或距离）。直径的两个端点称为直径端点。 性质与应用 图论基础：用于分析树的结构特征 网络优化：数据中心、通信网络中的延迟评估 算法设计：分治、动态规划的基础 竞技编程：树形DP问题中的常见模式 算法步骤 方法一：两次BFS/DFS
最小生成树（MST）—— Kruskal 贪心策略：每次选择权重最小的边加入生成树，同时避免形成环路 可用于解决最小网络，最低价联通之类的问题 例题 P3366 【模板】最小生成树 #
最近公共祖先 LCA 什么是 LCA 最近公共祖先（Lowest Common Ancestor，简称 LCA）是树上最基础的问题之一：在一棵有根树中，两个节点的所有公共祖先里，深度最大（离根最远）的那个节点，就是它们的 LCA。 举个例子：对于查询 (u,v)
欧拉路问题 Euler Path 欧拉路是图论中的经典问题，源于柯尼斯堡七桥问题。欧拉在 1736 年证明该问题无解，由此开创了图论这一数学分支。 定义 欧拉路径（Eulerian Trail）：通过图中每条边恰好一次的路径（顶点可重复）。 欧拉回路（Eulerian Circuit）：通过图中每条
