克隆图

关键不是背模板，而是看懂为什么这题适合图 · DFS/BFS。

1. 克隆入口 A，存哈希表：深拷贝整张图：从入口 A 开始 DFS。先克隆 A，存哈希表 map[A]=A'(原节点 → 克隆节点)。

2. 沿 A→B · 递归克隆 B：沿边 A→B：第一次见 B → 递归克隆 B，map[B]=B'，把 B' 接到 A' 的邻居表。

3. B 的邻居 A 已克隆 · 沿 B→C：B 的邻居里 A 已在 map → 直接取 A' 接边、不重复克隆；沿 B→C 递归克隆 C。

4. 沿 C→D · 递归克隆 D：沿 C→D：第一次见 D → 递归克隆 D，map[D]=D'。

5. 关键帧 · 哈希表挡住环：关键帧：沿 D→A，但 A 已在 map 里 → 直接取 A' 接边，不再递归。哈希表挡住了环 —— 否则 A→B→C→D→A→… 会无限递归。

6. 每节点克隆一次 · 返回 A'：每个节点只克隆一次、每条边都接到对应的克隆节点，返回入口的克隆 A'。时间 O(V+E)、空间 O(V)。

把这句话记住，下次遇到同类题，就能更快选出方向。

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。