题目大意

给定两个 $n$ 个节点的连通无向图（初始图和目标图），通过以下两种操作将初始图转换为目标图：

• 添加边：只能添加当前不存在的边，且必须存在一个节点与要连接的两个节点都相邻
• 删除边：只能删除已存在的边，且必须存在一个节点与要断开连接的两个节点都相邻

要求在 $200,000$ 次操作内完成转换。

算法思路

核心观察

1. 操作限制的本质：添加或删除边 $(u,v)$ 时，需要存在节点 $w$ 同时与 $u$ 和 $v$ 相邻。这意味着我们只能在三角形结构中进行操作。

2. 关键策略：利用图的连通性，我们可以通过维护一个生成树来保证操作的可行性。

具体解法

1. 生成树构建：

   • 在目标图中找到一个生成树 $T$
   • 这个生成树将作为我们操作的"骨架"

2. 操作过程：

   • 阶段1：在初始图中添加所有目标生成树 $T$ 中的边（如果不存在）
   • 阶段2：删除所有不在目标图中的边

3. 操作可行性保证：

   • 当添加边 $(u,v)$ 时，由于生成树 $T$ 是连通的，存在从 $u$ 到 $v$ 的路径
   • 我们可以沿着这条路径逐步构建三角形结构，最终添加目标边
   • 删除操作同理，通过维护连通性来保证存在公共邻居

实现细节

1. 生成树选择：使用 DFS 或 BFS 在目标图中构建生成树
2. 操作顺序：确保每次操作时图的连通性不被破坏
3. 操作计数：每个边最多需要 $O(n)$ 次操作，总操作数在 $O(nm)$ 范围内，满足题目限制

复杂度分析

• 时间复杂度：$O(n(m_s + m_d))$，其中 $n$ 是节点数，$m_s$ 和 $m_d$ 分别是初始图和目标图的边数
• 空间复杂度：$O(n + m_s + m_d)$

代码实现要点

// 伪代码框架
1. 读入初始图和目标图
2. 在目标图中构建生成树 T
3. 操作序列初始化
4. 对于 T 中的每条边 (u,v):
   - 如果初始图中不存在 (u,v)，则通过路径 u->...->v 逐步添加边
5. 对于初始图中的每条边 (u,v):
   - 如果目标图中不存在 (u,v)，则通过路径 u->...->v 逐步删除边
6. 输出操作序列

这种方法保证了在题目限制内完成图的转换，且操作序列满足所有的约束条件。