用显式栈替代递归、dfn/low数组用int并显式初始化为-1、预分配邻接表容量、缩点后去重边、有向图才适用tarjan；避免short溢出、vector缓存不友好及初始化疏漏。
tarjan() 函数怎么写才不会栈溢出
递归实现 tarjan() 时，深图容易触发栈溢出，尤其在竞赛或嵌入式环境里。系统默认栈空间小（windows 常为 1MB），而 DFS 深度可能上万。
- 用显式栈模拟递归：把
u、low[u]、dfn[u]、当前邻接点索引打包进结构体，避免函数调用开销和栈帧堆积 - 初始化
dfn和low数组必须用 -1 或 0 显式清零，不能靠局部变量默认值——c++ 全局/静态数组是 0，但堆上new int[n]是未定义值 - 别在
tarjan()内部反复vector<int>::push_back()</int>到栈中——每次扩容可能触发内存重分配，间接增加栈帧压力；预分配好邻接表容量更稳
dfn 和 low 数组为什么必须用 int 而不是 short
当节点数超过 32767，short 会溢出。看似省内存，实则导致 dfn[u] == 0 误判为“未访问”，进而重复入栈、死循环或漏缩点。
-
dfn是时间戳，最大值可达n（节点数），务必与n同量级类型：一般用int，超大图（>2e9）才考虑long long -
low[u]可能等于某个dfn[v]，所以类型必须和dfn严格一致，否则比较时隐式转换可能截断 - 常见错误：
vector<short> dfn(n);</short>+if (dfn[u] == 0)→ 在 n > 32767 时逻辑崩坏
缩点后建图为什么 edges 要去重
Tarjan 缩点后，原图中多个边可能映射到同一对 SCC 编号上，比如 u→v、w→v 且 u,w 同属 SCC A，v 属 SCC B，则生成两条 A→B 边——但 DAG 上不需要重边，会影响后续拓扑排序或 DP 的正确性。
- 用
set<pair int>></pair>或unordered_set（需自定义哈希）暂存边，再转成 vector - 更轻量做法：缩点时对每个 SCC 的出边目标用
vector<bool> used(scc_cnt + 1)</bool>标记，避免重复加边 - 注意：无向图不能直接套 Tarjan 缩点——它只适用于有向图；无向图连通分量该用并查集或 DFS/BFS
vector> graph 和 int** 性能差在哪
用 vector<vector>></vector> 存邻接表，遍历时 cache miss 高：每层 vector 的数据不连续，CPU 预取失效；而 int** 手动管理更麻烦，但若配合 vector<int> edges</int> + vector<int> head</int>（链式前向星），效率明显提升。
立即学习“C++免费学习笔记（深入）”；
- 小图（n vector
> 没问题，代码简洁 - 大图（n > 1e4）优先链式前向星：
head[u]指向下一条以 u 为起点的边在edges中的下标，edges[i]存终点，next[i]存下一条同起点边的下标 - 别忘了：Tarjan 过程中要遍历所有出边，
graph[u].size()是 O(1)，但graph[u][i]的地址跳转成本比连续数组高一截
实际写的时候，最常卡住的是 dfn 初始化不彻底、缩点后忘记判重边、以及递归过深——这些点没处理好，算法看起来对，跑大数据就静默错。