Problem description:

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

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

1
2
3
4
5
6
   1
  / \
 /   \
0 --- 2
     / \
     \_/

Solution:

Use a map to store every node that has already been copied. While adding every neighbor, call recursive function to apply dfs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        visited = {node: Node(node.val)}
        self.dfs(node, visited)
        return visited[node]
    
    def dfs(self, node, visited):
        for neighbor in node.neighbors:
            if neighbor not in visited:
                visited[neighbor] = Node(neighbor.val)
                self.dfs(neighbor, visited)
            visited[node].neighbors.append(visited[neighbor])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    //use map to store the nodes that have already been copied
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> map;
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return NULL;
        if(map.find(node) == map.end()){ //not cloned yet
            UndirectedGraphNode* tmp= new UndirectedGraphNode(node->label);
            map[node]= tmp;
            for(auto n: node->neighbors){
                tmp->neighbors.push_back(cloneGraph(n));
            }
        }
        return map[node];
    }
};

Solution BFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        # BFS
        if not node:
            return node
        queue = deque([node])
        visited = {node: Node(node.val)}
        while queue:
            front = queue.popleft()
            for neighbor in front.neighbors:
                if neighbor not in visited:
                    newNode = Node(neighbor.val)
                    visited[neighbor] = newNode
                    queue.append(neighbor)
                visited[front].neighbors.append(visited[neighbor])
        return visited[node]

time complexity: $O(V+E)$
space complexity: $O(n)$
reference:
https://goo.gl/BGsAmT