I devised a twopass procedures to solve this problem, using hash map and BFS.

BFS the graph from the given node. For each node n, clone it as new node m, and set map map[n]=m.

For each n in map's keys, we update the neighbor relationships. For each neighbor nn in n.neighbors, we have mm=map[nn] then we add mm into map[n].neighbors.
The pseudocode, python code, and C++ code can be found in my blog here. However, I only paste my python code here. I tried python first and got LTE, then I translated the python code into C++ using <vector> and <map>, finally got accepted.
Can anyone help me with improving my python code below? THANKS!
# 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
def cloneGraph(self, node):
"""
Similar to the previous problem "Copy List with Random Pointer"
which deepcopies a list node containing (value, next, random).
So we can use similar technique.
We need to assume that each node has a path to the given node
"""
# Special case:
if node is None:
return None
# We use a dictionary to map between the original node and its copy
# Also, we can use mapping.keys() to keep track the nodes we already visited
mapping = {}
# BFS from the given node
q = [node]
while q:
# I do not pop/push on q, since it is not efficient for python buildin list structure
# Instead, I just create a new empty list, and iterate all elements in q
# After adding all neighbors to new_q, set q = new_q
new_q = []
for n in q:
# Clone n and map it with its clone
mapping[n] = UndirectedGraphNode(n.label)
# Check its neighbors
for x in n.neighbors:
if x not in mapping.keys():
new_q.append(x)
q = new_q
# All nodes are mapping.keys()
for n in mapping.keys():
for x in n.neighbors:
mapping[n].neighbors.append(mapping[x])
# Return the clone of node
return mapping[node]