133. Clone Graph

The intuition is to use DFS/BFS. I'm using DFS here. We should note that nodes are uniquely labeled which indicates that we can use label to set up a hash table. So the key-value pair will be the label and the new node. The reason we want to use hash table is to avoid duplicates. For example, we have <0, 1>. So for 0, it has neighbor 1 and for 1 it has neighbor 0. When we start from 0, we'll copy a node of 0 and then visit 1. When visiting 1, we know there's 0 but at that time, we don't want to copy 0 again as we already did. All we want to do it just push the pointer to 1's neighbor list.

1:  /**  
2:   * Definition for undirected graph.  
3:   * struct UndirectedGraphNode {  
4:   *   int label;  
5:   *   vector<UndirectedGraphNode *> neighbors;  
6:   *   UndirectedGraphNode(int x) : label(x) {};  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {  
12:      if (node == NULL) return NULL;  
13:      unordered_map<int, UndirectedGraphNode*> visited;  
14:      return dfs(node, visited);  
15:    }  
16:    UndirectedGraphNode *dfs(UndirectedGraphNode *node, unordered_map<int, UndirectedGraphNode*> &visited) {  
17:      UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);  
18:      visited[node->label] = newNode;  
19:      for (UndirectedGraphNode* n : node->neighbors) {  
20:        if (!visited[n->label]) {  
21:          newNode->neighbors.push_back(dfs(n, visited));  
22:        } else {  
23:          newNode->neighbors.push_back(visited[n->label]);  
24:        }  
25:      }  
26:      return newNode;  
27:    }  
28:  };  

Here is the BFS way.

1:  /**  
2:   * Definition for undirected graph.  
3:   * struct UndirectedGraphNode {  
4:   *   int label;  
5:   *   vector<UndirectedGraphNode *> neighbors;  
6:   *   UndirectedGraphNode(int x) : label(x) {};  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {  
12:      if (node == NULL) return NULL;  
13:      unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> mp;  
14:      UndirectedGraphNode *root = new UndirectedGraphNode(node->label);  
15:      mp[node] = root;  
16:      queue<UndirectedGraphNode *> q;  
17:      q.push(node);  
18:      while(!q.empty()) {  
19:        UndirectedGraphNode *cur = q.front();  
20:        q.pop();  
21:        for (UndirectedGraphNode *neighbor : cur->neighbors) {  
22:          if (mp.find(neighbor) == mp.end()) {  
23:            UndirectedGraphNode *copy = new UndirectedGraphNode(neighbor->label);  
24:            mp[neighbor] = copy;  
25:            q.push(neighbor);  
26:          }  
27:          mp[cur]->neighbors.push_back(mp[neighbor]);  
28:        }  
29:      }  
30:      return root;  
31:    }  
32:  };  

When I revisited this problem again, I found a more concise DFS way.

1:  /**  
2:   * Definition for undirected graph.  
3:   * struct UndirectedGraphNode {  
4:   *   int label;  
5:   *   vector<UndirectedGraphNode *> neighbors;  
6:   *   UndirectedGraphNode(int x) : label(x) {};  
7:   * };  
8:   */  
9:  class Solution {  
10:  private:  
11:    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;  
12:  public:  
13:    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {  
14:      if (node == NULL) return NULL;  
15:      UndirectedGraphNode *root = new UndirectedGraphNode(node->label);  
16:      mp[node] = root;  
17:      for (UndirectedGraphNode *n : node->neighbors) {  
18:        if (mp.find(n) == mp.end()) root->neighbors.push_back(cloneGraph(n));  
19:        else root->neighbors.push_back(mp[n]);  
20:      }  
21:      return root;  
22:    }  
23:  };