# Clone Graph

{% embed url="<https://www.lintcode.com/problem/137/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) {
 *         label = x;
 *         neighbors = new ArrayList<UndirectedGraphNode>();
 *     }
 * }
 */

public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return node;
        Map<UndirectedGraphNode, UndirectedGraphNode> oldToNew = new HashMap<>();
        Queue<UndirectedGraphNode> q = new ArrayDeque<>();
        q.offer(node);
        oldToNew.put(node, new UndirectedGraphNode(node.label));

        while (!q.isEmpty()) {
            UndirectedGraphNode curr = q.poll();
            for (UndirectedGraphNode nei : curr.neighbors) {
                if (!oldToNew.containsKey(nei)) {
                    oldToNew.put(nei, new UndirectedGraphNode(nei.label));
                    q.offer(nei);
                }
                oldToNew.get(curr).neighbors.add(oldToNew.get(nei));
            }
        }
        return oldToNew.get(node);
    }
}
```

### Notes

* The `oldToNew` map has two functions here:
  * It keeps track of which nodes are visited. If the map already contains a node, we do not add it to the queue.
  * It creates a mapping between old nodes and new nodes. We can directly get new node from their corresponding old nodes.


---

# 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://blog.yushunchen.com/algo/bfs/2.-connected-graph-and-topologic-sorting/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.