题解：qoj#1824 Special Cycle

· · 题解

题目大意

给定一个 n 个点，m 条边的简单无向图，其中 K 条边是特殊边。要求构造一个简单环，使得所有特殊边要么在环上，要么两个端点都不在环上，或报告无解。

时间限制 $12s$。 ### 解法 考虑有解的条件。 如果一个点在环上，那么它相邻的所有特殊边都应该在环上。所以取出所有特殊边的子图中每个连通块同时在环中或者同时不在，那么一个连通块有几种可能： 1. 存在一个度数大于等于 $3$ 的点，则连通块中所有点都不能出现在答案中，全部删去； 2. 是一个环，则可以直接作为答案； 3. 是一条链，那么中间的二度点的所有非特殊边都没用，可以缩成一条边； 4. 是一个单点。 现在问题转化成了所有特殊边都没有公共顶点的情况。接下来不断重复以下流程： 1. 图中所有割边也不能在环中，将所有割边删去； 2. 如果一条特殊边删去，它的端点也不能在答案中，也删去。 如果最后图被删空，否则可以证明剩下的图上可以构造出解。 :::info[证明] 我们通过对点数的归纳进行证明。点数不超过 $3$ 的情况是显然的。 下面考虑更大的图。先假设所有边都不特殊，那么由边双连通性一定可以找到一个简单环。接下来依次考虑三种类型的每条特殊边 $e$，并时刻找到一个在当前每条边特殊性下合法的环： 1. 如果 $e$ 在环上或与环无交，则直接合法； 2. 如果 $e$ 的两个端点都在环上，那么环上与 $e$ 相邻的四条边都不是特殊的，所以取出这个环一边的弧和 $e$ 共同组成环即可； 3. 如果 $e$ 的恰好一个端点在环上，那么将这个环所成一个点。由于在 $e$ 变为特殊前环合法，所以缩点后这个点相邻的特殊边也只有 $e$ 一条，同时不难说明边双连通性仍然保持，所以由归纳假设在这个新图上存在合法的环（这里的合法只考虑了 $e$ 和在 $e$ 之前变为特殊的边）。那么这个新图上环要么和原来的环无交，要么经过 $e$，不难发现也可以取出环上的一边的弧构造出在原图上合法的环。 ::: 上面的证明实际上就描述了一个算法，不过归纳证明使得这个算法有些复杂。 既然得到了图合法的条件，那么可以考虑依次尝试删除每条边（如果是特殊边同时也删去端点），如果删边后不合法，则这条边要保留，否则就删去这条边，这样最后一定会得到一个环。 这个算法还可以进行一个小优化（对于下面的复杂度证明十分重要）：如果成功删除一条边，在检验删除这条边是否合法的过程中会不断删去割边，接下来只需要在最后剩下的边双连通图上继续尝试删边。 这个算法的复杂度瓶颈在于找割边/边双连通分量，所以下面分析找割边的次数。 首先，尝试删除每条边后要先找一次割边，总共 $O(m)$ 次，接下来： 1. 如果成功删除，那么每次再找割边一定是因为上次找到的割边中有特殊边，导致删去这条边时也删去了端点。由于上面的优化，这些删除的点再也不会出现，所以这部分最多额外找 $O(n)$ 次割边。 2. 如果删除失败，那么同上判定过程中也至多找了 $O(n)$ 次割边。但由于删除失败要还原图，所以这 $O(n)$ 次不能摊到整张图上。但是注意到删除失败意味着找到了一条必须在答案中的边，而答案是简单环所以至多 $O(n)$ 条边，所以至多删除失败 $O(n)$ 次，总共 $O(n^2)$ 次找割边。 综上，至多找 $O(n^2+m)$ 次割边，总复杂度可以用 tarjan 算法做到 $O((n^2+m)(n+m))$ 或用 bitset 优化 Kosaraju 算法做到 $O((n^2+m)(\frac{n^2}{w}+n))$。