# 133 Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

**The Idea:** To clone a graph, we will have to copy every node within the graph. However, because each node carries a collection of neighbor that are points, the we need to avoid any extra copying. For example, say our graph is:

```
1: 1,2
2: 1,3
```

Even though 1 is connected to itself, and 2 is connect to 1, both these 1s have the same address. So as we iterate through the graph, we need to map the existing address of a node to the address of the copy which is the new node. Only when the memory is not mapped do we create a new node, and when the memory is mapped, we can return the same address which is the copy of the new node.

**Complexity:** O(n) time and space

```cpp
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return nullptr;
        if (!mem.count(node)) {
            mem[node] = new UndirectedGraphNode(node->label);
            for (auto &neighbor : node->neighbors) {
                // we've already mapped the node, so mem[node] references the new address
                mem[node]->neighbors.push_back(cloneGraph(neighbor));
            }
        }
        return mem[node];
    }

private:
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mem;
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/133-clone-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.