SCCPC2026 K 环基基环树题解

发表于 2026-06-22 分类于题解

原图是一棵基环树。变异时，每个原图点被替换成一个长度至少为的环；原图中的每条边，则变成两个环之间的一条连边。

我们的目标不是恢复唯一的原图，而是输出任意一张同构的基环树。因此只要能把每个“被扩出来的环”重新识别成一个点，再把环与环之间的边连回去即可。

先看变异后的边会分成哪几类：

所以第一步很自然：在变异后的图中找出所有桥，并把这些桥先删掉。

删掉桥之后，树枝部分的连接被断开了；而每个扩展环本身仍然存在，原图基环上的环间连接也仍然存在。

接下来考虑删桥后的度数。

对于某个扩展环，如果环上的一个点没有承担原图基环上的连接边，那么它只连着环内左右两个邻点，度数就是。如果它承担了基环上的连接边，那么除了两个环内邻点外，还会连到别的扩展环，度数至少为。

因为原图是基环树，一个点在基环上最多只会连出两条非桥边；又因为每个扩展环长度至少是，所以每个扩展环里一定能找到度数为的点。

这个度数为的点很有用：在删桥后的图里，它的两条边一定都是环内边，因此它和它的两个邻点一定来自原图中的同一个点。我们可以把这三个点合并。

不断重复这个过程，同一个扩展环中的所有点最终都会被合并到一起。不同扩展环之间不会被错误合并，因为跨环连接的端点在删桥后度数至少为，不会作为“度数为的中间点”去把两边粘起来。

完成缩点后，每个缩点就对应原图中的一个点。

最后重新扫描变异后图的所有边。设一条边的两个端点分别属于缩点：

这样得到的图就是一张合法的基环树。

找桥、缩点和扫描边都可以线性完成，时间复杂度和空间复杂度都是。