tarjan算法需用vector模拟栈、全局时间戳、遍历所有未访问节点；dfn和low首次进入即赋值，回溯用min(low[u], low[v])更新；缩点前必须清空所有状态数组。
tarjan() 函数怎么写才不会栈溢出或漏节点
直接用递归实现 tarjan() 很容易在稠密图或深链图上爆栈，或者因未正确维护 low[] 和 dfn[] 导致某个强连通分量被拆开。核心是：递归入口必须覆盖所有未访问节点；每个节点的 dfn[u] 和 low[u] 必须在第一次进入时立刻赋值；回溯时用 min(low[u], low[v]) 更新，而非 min(low[u], dfn[v])（后者只适用于判断桥/割点）。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 用
vector<vector>></vector>存邻接表，避免 map 或 set 带来常数开销 - 全局计数器
timestamp初始化为 0，每次进 dfs 就dfn[u] = low[u] = ++timestamp - 入栈操作放在 dfs 开头，出栈必须严格匹配：仅当
dfn[u] == low[u]时才循环弹出直到u - 别忘了对每个
i从0到n-1调用dfs(i)—— 图不保证连通
stack 和 vector 哪个更适合存栈
用 stack<int></int> 语义清晰，但实际调试时没法遍历、打印中间状态；而 vector<int></int> + push_back()/pop_back() 完全等价，还能随时用 back() 查顶、用 size() 看长度、甚至输出整个栈内容排查问题。性能无差异，STL vector 的 push_back 在末尾是均摊 O(1)。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 声明为
vector<int> stk;</int>，不是stack<int></int> - 入栈：
stk.push_back(u); - 出栈到强连通分量：
while (stk.back() != u) { int x = stk.back(); stk.pop_back(); comp[x] = comp_id; } stk.pop_back(); comp[u] = comp_id; - 别用
stk.empty()做循环条件——你得靠dfn[u] == low[u]触发出栈逻辑
有向图含重边或自环时 tarjan 会错吗
标准 tarjan 对重边和自环天然鲁棒：自环 u→u 会让 dfn[u] 成立，自然被归入自身所在 SCC；重边只是多一次 <code>v == u 或 dfn[v] > 0 的判断，不影响 low 更新逻辑。真正要防的是建图时把反向边误加进去（比如无向图当有向图跑），或者邻接表里混入非法索引。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 建图后检查：所有
v是否满足0 - 遇到
u == v（自环）无需跳过，正常处理 - 遇到已访问节点
v且v在栈中，才更新low[u] = min(low[u], dfn[v])；如果v已出栈，跳过 - 用
in_stk[v]数组标记，而不是查栈里有没有——vector栈没法高效查找
LeetCode 1192 那种“关键连接”能直接套 tarjan 吗
不能。那是无向图求桥（bridge），要用类似 tarjan 的思想，但更新规则不同：对无向图，不能用 dfn[v] 更新 low[u]（否则会把父边误判为后向边），得记录父节点并跳过。而且不需要栈、不需要 SCC 编号，只关心 low[v] > dfn[u] 是否成立。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 有向图 SCC → 用带栈 +
dfn/low+in_stk的完整 tarjan - 无向图找桥 → 去掉栈相关逻辑，加
parent参数，更新时写if (v != parent) low[u] = min(low[u], dfn[v]); - 同一个项目里混用两种逻辑？务必分开函数名，比如
find_scc()和find_bridges()，别共用一个tarjan()
最常被忽略的一点：缩点后的新图一定是 DAG，但如果你在原图上反复调用 tarjan() 却没清空 dfn[]、low[]、stk、in_stk[]，下一轮结果就全乱了。每次运行前重置这些数组，比 debug 半小时更省时间。
