如何基于双连通分量构建新图？能否在运行Tarjan算法时完成？

方案1：基于已有的双连通分量、割点结果构建 #

这个方法实现起来最简单，时间复杂度也达到最优，步骤如下：

• 第一步：给每个双连通分量分配唯一的标识ID，同时构建割点-关联分量映射表：遍历所有双连通分量，对每个分量内的所有顶点做判断，若该顶点是割点，就将当前分量ID追加到该割点对应的关联分量列表中。
• 第二步：遍历所有割点的关联分量列表，对列表中所有的分量ID两两加边即可。如果需要避免重复加边，可以用哈希集合做去重，或者邻接表双向添加时做重复判断。

以你给出的示例为例：
割点1的关联分量列表为[(1,3), (1,2)]，因此给这两个分量加边；割点3的关联分量列表为[(1,3), (3,4,5)]，因此给这两个分量加边，最终得到的邻接表和你给出的示例完全一致。

这个方法的时间复杂度为线性的O(V+E)，和原图的顶点、边规模成正比，是理论最优的实现方案。

方案2：Tarjan算法运行过程中同步构建 #

完全可以在Tarjan算法找双连通分量的过程中同步完成缩点建图，不用等所有分量和割点都识别完再单独跑构建逻辑，实现逻辑如下：

• Tarjan算法找双连通分量时会用栈存储遍历过的边，当我们判定当前节点是割点、要从栈中弹出边得到一个完整双连通分量时，直接给这个新分量分配ID。
• 遍历这个新分量的所有顶点，筛选出其中已经被标记完成的割点（注意根节点的割点判定需要等所有子树遍历完成才能确认，因此需要单独延后处理），将当前分量ID添加到这些割点的关联分量列表中。只要同一个割点的关联分量列表长度≥2，就可以直接给最新加入的分量和列表中已有的分量加边，不需要等到所有处理完成。
• 所有子树遍历完成后，额外判断根节点是否为割点（判定条件为根节点的子树数量≥2），如果是割点，就把根节点关联的所有分量两两加边即可。

这个方案和标准Tarjan算法的时间复杂度完全一致，不需要额外的遍历开销，整体效率更高。

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