qoj1824 一个也许更简单的做法

qczrz6v4nhp6u · 2025-10-30 21:58:48 · 个人记录

Solution

定义关键点为与某些关键边相邻的点。

首先判一下是否存在由关键点构成的环，若有就直接输出。

然后把所有关键边的连通块找出来。对于每个连通块：

• 若这是环，直接选它作为答案即可；
• 若这是链，则选了一端后一定会选另一端，我们把这一整条链缩为一条关键边即可；
• 否则这啥也不是，最终答案一定不能碰到这个连通块，直接把这个连通块包含点所有点删掉即可。

现在我们将问题转化为了所有关键边不相交的问题。不难发现此时答案一定是关键边与非关键边交替的形式。

考虑处理出每两个关键点之间，不经过其他关键点能否互相到达。建一个只包含关键点的新图，将原图的关键边在新图上连一条实边，将能够不经过其他关键点互相到达的关键点对之间连一条虚边，则新图上一个虚实交替的简单环对应原图中一个 不一定简单 的合法环，这里不一定简单是因为两条虚边在原图对应的路径可能相交。

考虑在新图上找到一个虚实交替的简单环，这个以每条边为状态，bfs 一下看有没有环即可。然后处理一下对应到原图不简单的情况，只需要找到重复的那个点，从中间断开即可。

目前没写，但是口胡感觉很有道理啊！！！

upd：过了。

upd：好像假了，找虚实交替的简单环部分的做法大概是有问题的，但还是很神秘的过了。不知道有没有人能卡一下。

Code

这份代码 的复杂度大概是 O(nm) 的，但是感受到可以精细实现变成 O(n^2)，进一步发掘性质或许还能做到更优。