Let us clone a graph with no cycles — just a simple tree. Node by node, we recursively visit each node, create a copy, and connect the edges. At each step, predict what the algorithm should do.
Watch what happens at each step. Node by node, DFS creates a copy and records it in a HashMap. When DFS finishes with a node, it returns the clone — so the parent can wire up the edge. Every node visited once. Every clone registered exactly once. This is the simple version, and it works perfectly.
DFS visits node 1. What should the algorithm do?