技术求助：如何识别强连通分量（SCC）之间的连接边？

嘿，你已经用Tarjan算法把所有强连通分量（SCC）都挖出来了，这步已经搞定最核心的部分啦！针对你提到的两个思路，我给你拆解下具体怎么落地实现：

这个思路不需要真的删除内部边，只需要给每个节点打上所属SCC的标记，就能快速筛选出跨SCC的边：

• 第一步，给每个节点分配SCC ID：用一个数组component_id[]，数组下标对应节点编号，值就是该节点所属SCC的唯一标识（比如从0开始递增的整数）。Tarjan算法执行过程中，其实可以顺便完成这个标记工作。
• 第二步，遍历原图的所有边u → v：对每条边，检查component_id[u]和component_id[v]是否相等。如果不相等，这条边就是你要找的不同SCC之间的连接边；如果相等，那就是SCC内部的边，直接跳过即可。
• 这个方法时间复杂度是O(V+E)，和Tarjan算法本身复杂度一致，高效且不需要额外构建新图。

如果后续还要对跨SCC的连接做更多分析（比如找拓扑序、关键路径等），构建缩点图会更方便：

• 同样先给每个节点分配SCC ID，这是基础。
• 创建新的图结构，把每个SCC当作一个“超级顶点”。
• 遍历原图的所有边u → v：当component_id[u] != component_id[v]时，在缩点图中添加一条从component_id[u]到component_id[v]的边。这里要注意去重——原图中可能有多条边连接同一对SCC，缩点图里只需要保留一条即可（可以用哈希集合或邻接表加判断实现去重）。
• 缩点后的图是一个有向无环图（DAG），这个图里的所有边，就对应原图中不同SCC之间的连接边，后续操作逻辑会更清晰。

实用小提示 #

• 如果你的需求只是检测是否存在跨SCC边，不需要收集所有边的话，遍历原图边时，只要找到第一条满足component_id[u] != component_id[v]的边，就可以直接返回“存在”，能节省不少时间。
• 自环边（u == v）肯定是SCC内部边，遍历的时候可以直接跳过，不用做判断。
• 两种思路本质相通，选哪种取决于你后续需求：只是找跨分量边，思路一更简单；要做更多DAG相关操作，思路二更合适。

内容的提问来源于stack exchange，提问作者Miki Bakaiki