SCCPC2026 K 环基基环树 题解
题目链接：QOJ Contest 3789 Problem K
原图是一棵基环树。变异时，每个原图点被替换成一个长度至少为 $3$ 的环；原图中的每条边，则变成两个环之间的一条连边。
我们的目标不是恢复唯一的原图，而是输出任意一张同构的基环树。因此只要能把每个“被扩出来的环”重新识别成一个点，再把环与环之间的边连回去即可。
先看变异后的边会分成哪几类：
- 扩展环内部的边；
- 原图基环上的边，对应扩展环之间的非桥；
- 原图基环外树枝上的边，对应扩展环之间的桥。
所以第一步很自然：在变异后的图中找出所有桥，并把这些桥先删掉。
删掉桥之后，树枝部分的连接被断开了；而每个扩展环本身仍然存在，原图基环上的环间连接也仍然存在。
接下来考虑删桥后的度数。
对于某个扩展环 $C_x$，如果环上的一个点没有承担原图基环上的连接边，那么它只连着环内左右两个邻点，度数就是 $2$。如果它承担了基环上的连接边，那么除了两个环内邻点外，还会连到别的扩展环，度数至少为 $3$。
因为原图是基环树，一个点在基环上最多只会连出两条非桥边；又因为每个扩展环长度至少是 $3$，所以每个扩展环里一定能找到度数为 $2$ 的点。
这个度数为 $2$ 的点很有用：在删桥后的图里，它的两条边一定都是环内边，因此它和它的两个邻点一定来自原图中的同一个点。我们可以把这三个点合并。
不断重复这个过程，同一个扩展环中的所有点最终都会被合并到一起。不同扩展环之间不会被错误合并，因为跨环连接的端点在删桥后度数至少为 $3$，不会作为“度数为 $2$ 的中间点”去把两边粘起来。
完成缩点后，每个缩点就对应原图中的一个点。
最后重新扫描变异后图的所有边。设一条边的两个端点分别属于缩点 $U,V$：
- 如果 $U=V$，它是扩展环内部的边，忽略；
- 如果 $U\ne V$，它对应原图中的一条边，输出这条缩点之间的边。
这样得到的图就是一张合法的基环树。
找桥、缩点和扫描边都可以线性完成，时间复杂度和空间复杂度都是 $O(n+m)$。