**Solution 2** (A better solution)

```
# Definition for a undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
# 2:41
def cloneGraph(self, node):
if not node:
return None
newHead = UndirectedGraphNode(node.label)
queue = collections.deque([(node, newHead)])
map = {}
while queue:
cur, newCur = queue.popleft()
if cur in map:
continue
for child in cur.neighbors:
newChild = map.get(child, None) or UndirectedGraphNode(child.label)
newCur.neighbors.append(newChild)
queue.append((child, newChild))
map[cur] = newCur
return newHead
```

**Solution 1**

```
# Definition for a undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
# 2:04
def cloneGraph(self, node):
if not node:
return None
newHead = UndirectedGraphNode(node.label)
map = {node: newHead}
queue = collections.deque([node])
while queue:
cur = queue.popleft()
for neighbor in cur.neighbors:
if neighbor not in map:
newNeighbor = UndirectedGraphNode(neighbor.label)
map[cur].neighbors.append(newNeighbor)
queue.append(neighbor)
map[neighbor] = newNeighbor
else:
map[cur].neighbors.append(map[neighbor])
return newHead
```