Clone Graph
Return a deep copy of a connected undirected graph. (In the playground, the graph is an adjacency list: entry i lists the neighbours of node i + 1.)
A way to picture it
You're photocopying a friendship network. Each time you meet someone new, you make their twin first, and only then copy their friendships. A register of who already has a twin stops you from copying the same person twice, even when friendships loop back around.
How to approach it
DFS with a map from original → clone. Create and register a node's clone before visiting its neighbours; if a neighbour is already registered, reuse its clone.
Example
Input: {"adjList":[[2,4],[1,3],[2,4],[1,3]]}. Output: [[2,4],[1,3],[2,4],[1,3]].
Complexity: O(V + E) time and O(V) space. Each node is cloned once and each edge is copied once per direction.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.