图中桥计数测试遇随机StackOverflow问题求助（10万+顶点）

兄弟，这个问题我太熟了！你遇到的随机StackOverflow大概率是递归版Tarjan算法的栈溢出问题，跟你第9行的to= j.next直接相关，具体原因和解决办法给你掰扯清楚：

问题根源 #

统计桥的经典算法是Tarjan算法，很多人一开始会写递归实现——递归调用时每一层都会占用JVM的栈帧空间。但JVM的默认栈空间非常小（一般只有几百KB），当你处理10万+顶点的用例时：

• 如果图是链式结构（比如1→2→3→…→100000），递归深度会直接拉到10万层，这时候栈帧堆起来直接超过JVM的栈上限，触发StackOverflow；
• 如果图是星型/浅层次结构，递归深度只有几层，完全不会爆栈。

这就是为啥错误随机出现的原因——全看测试用例的图结构！你第9行的to= j.next应该是递归遍历邻接点时的代码，这时候栈已经撑不住了，自然就报错。

解决办法 #

1. 改成迭代版Tarjan算法（首选） #

把递归逻辑改成手动模拟栈的迭代实现，所有状态（当前节点、父节点、邻接点迭代器、dfn/low值、是否已处理标记等）都存在堆内存的栈结构里。堆的容量比JVM栈大得多，10万级别的顶点完全能hold住。

举个核心思路：

• 栈中每个元素存储「当前节点u、父节点parent、邻接点迭代器、是否已完成第一次访问的标记」；
• 第一次弹出节点时，初始化dfn和low值，然后把节点重新压回栈（标记为已访问），再把所有未访问的邻接点压入栈；
• 第二次弹出已标记的节点时，回溯更新low值，判断是否是桥。

2. 临时调大JVM栈大小（不推荐长期用） #

运行程序时加上-Xss参数增大栈容量，比如：

java -Xss10m YourProgramName

但这只是治标不治本——万一碰到更深的结构还是会爆，而且过大的栈会抢占堆内存，容易引发其他内存问题。

内容的提问来源于stack exchange，提问作者Popeye The Sailor