| 25 | } |
| 26 | |
| 27 | GraphNode* dfs(GraphNode* node, std::unordered_map<GraphNode*, GraphNode*>& cloneMap) { |
| 28 | // If this node was already cloned, then return this previously |
| 29 | // cloned node. |
| 30 | if (cloneMap.find(node) != cloneMap.end()) { |
| 31 | return cloneMap[node]; |
| 32 | } |
| 33 | // Clone the current node. |
| 34 | GraphNode* clonedNode = new GraphNode(node->val); |
| 35 | // Store the current clone to ensure it doesn't need to be created |
| 36 | // again in future DFS calls. |
| 37 | cloneMap[node] = clonedNode; |
| 38 | // Iterate through the neighbors of the current node to connect |
| 39 | // their clones to the current cloned node. |
| 40 | for (GraphNode* neighbor : node->neighbors) { |
| 41 | GraphNode* clonedNeighbor = dfs(neighbor, cloneMap); |
| 42 | clonedNode->neighbors.push_back(clonedNeighbor); |
| 43 | } |
| 44 | return clonedNode; |
| 45 | } |