如何高效查找连接两个SCC的弧？能否在Tarjan算法中线性实现？

好问题！完全可以做到无需额外遍历所有节点，甚至能在Tarjan算法执行的过程中同步识别跨SCC的弧，而且整个过程可以保持线性时间复杂度O(V+E)，这也是该问题的最优复杂度（毕竟你至少要处理每个节点和边一次才能完成判断）。下面分两种场景具体说明：

一、在Tarjan算法执行时同步识别跨SCC弧 #

Tarjan算法本身基于深度优先搜索（DFS），在遍历过程中维护每个节点的dfn（发现时间）和low（能回溯到的最早发现节点的时间），当某个节点u满足low[u] == dfn[u]时，就确定了以u为根的一个SCC。在处理每个节点的邻接边时，我们可以直接判断这条边是否跨SCC：

• 对于边u -> v：
  1. 如果v未被访问过：继续递归DFS访问v，DFS返回后，若low[v] > dfn[u]，说明v所在的SCC无法回溯到u的SCC，这条边u->v就是跨SCC的弧。
  2. 如果v已被访问且在当前DFS递归栈中：说明u和v属于同一个SCC，这条边不是跨SCC的。
  3. 如果v已被访问且不在递归栈中：说明v属于已经处理完成的SCC，这条边u->v必然是跨SCC的弧。

这种方式下，每条边只会在DFS过程中被处理一次，不需要额外遍历所有节点，完全嵌入Tarjan的流程中，整体时间复杂度保持线性。

二、得到所有SCC后快速筛选跨SCC弧 #

如果你已经通过Tarjan或其他算法（比如Kosaraju）得到了每个节点所属的SCC编号（比如用数组scc_id[]存储每个节点对应的SCC ID），那么只需要遍历所有边一次即可筛选出跨SCC的弧：
对每条边u->v，只需判断scc_id[u] != scc_id[v]——如果成立，这条边就是连接不同SCC的弧。

这个过程的时间复杂度是O(E)，属于线性时间，而且不需要遍历所有节点，只需要遍历边集合即可（当然，前提是你已经有了边的列表或者能高效遍历所有邻接边）。

关键说明 #

所谓“无需遍历所有节点”，本质是指不需要在SCC计算完成后再额外做一轮全节点遍历。不管哪种方法，我们都只需要处理所有边一次（要么在Tarjan的DFS中，要么在后续的边筛选中），而处理边的总次数是线性的，符合最优复杂度要求。

内容的提问来源于stack exchange，提问作者Miguel Barros