在Tarjan算法中，我们只能使用一个索引数组吗

Question

在Tarjan算法中，有两个索引数组，一个按照发现节点的顺序对节点进行连续编号。另一个表示从v通过v的子树可以到达的最小索引，这是算法的伪代码

tarjan(u)
{
DFN[u]=Low[u]=++Index                      
Stack.push(u)                            
for each (u, v) in E                    
if (v is not visted)              
tarjan(v)                
Low[u] = min(Low[u], Low[v])
else if (v in S)                  
Low[u] = min(Low[u], DFN[v])
if (DFN[u] == Low[u])                      
repeat
v = S.pop                  
print v
until (u== v)
}

但我认为低阵列可以去掉，算法改为

tarjan(u)
{
if(DFN[u]) // assume all elements in DFN is initialized to 0
return DFN[u]
DFN[u]=++Index                      
Stack.push(u)      
res = DFN[u]                     
for each (u, v) in E                                          
res = min(res, tarjan(v))
if (DFN[u] == res)                      
repeat
v = S.pop                  
print v
until (u== v)
return res
}

我在小图上做了一些测试，结果与标准tarjan相同。但我不确定它是否能成功地在各种图中找到强连通分量。这个算法是正确的还是只能通过弱测试用例。

Answer 1

我同意MrSmith42的观点，即详尽列举小例子是获得信心的好方法。

然而，即使添加了缺失的return res，我认为您的算法仍然不正确。双顶点图，2→1.如果我们遍历1，然后遍历2，则2的res的值将为1，导致{2}作为强分量被遗漏。