@ 今天突然看到这个帖，不知道你还要不要，但也给你浅讲一下吧

一、核心概念

时间戳（dfn数组）‌

记录节点首次被访问的顺序编号，每个节点在DFS过程中被首次访问时分配唯一递增的整数。

追溯值（low数组）‌

表示当前节点通过非父子边（后向边或横向边）能回溯到的最小dfn值。初始时low[u] = dfn[u]，在DFS过程中通过邻接节点动态更新。

int dfn[MAXN], low[MAXN], idx = 0;

二、应用场景

1. 强连通分量（有向图）

‌判定条件‌：当回溯时满足$dfn[u] == low[u]$，栈中从u到栈顶的节点构成一个强连通分量。

‌栈的使用‌：DFS过程中将节点压栈，找到强连通分量后弹出

2. 桥检测（无向图）

‌判定条件‌：对于边$(u, v)$，若$low[v] > dfn[u]$，则该边为桥。 ‌ 父节点处理‌：需记录父节点避免重复访问。

3. 割点检测（无向图）

‌判定条件‌：

根节点：若有$≥2$个子树则为割点。

非根节点：存在子节点$v$使得$low[v] >= dfn[u]$