leetcode/algorithms/clone_graph.cpp at master · hanfezh/leetcode · GitHub

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
 * =====================================================================================
 *
 *       Filename:  clone_graph.cpp
 *
 *    Description:  133. Clone Graph. https://leetcode.com/problems/clone-graph/
 *
 *        Version:  1.0
 *        Created:  03/29/23 21:42:31
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  xianfeng.zhu@gmail.com
 *   Organization:
 *
 * =====================================================================================
 */
#include <queue>
#include <unordered_map>
#include <vector>

using std::queue;
using std::unordered_map;
using std::vector;

class Node {
 public:
  int val;
  vector<Node*> neighbors;

  Node() {
    val = 0;
    neighbors = vector<Node*>();
  }

  Node(int _val) {
    val = _val;
    neighbors = vector<Node*>();
  }

  Node(int _val, vector<Node*> _neighbors) {
    val = _val;
    neighbors = _neighbors;
  }
};

// Depth first search
class Solution1 {
 public:
  Node* cloneGraph(Node* node) {
    if (node == nullptr) {
      return node;
    }

    auto it = all_nodes_.find(node);
    if (it != all_nodes_.end()) {
      return it->second;
    }

    Node* clone = new Node(node->val);
    all_nodes_[node] = clone;
    for (auto* n : node->neighbors) {
      clone->neighbors.push_back(cloneGraph(n));
    }
    return clone;
  }

 private:
  unordered_map<Node*, Node*> all_nodes_;
};

// Breadth first search
class Solution2 {
 public:
  Node* cloneGraph(Node* node) {
    if (node == nullptr) {
      return node;
    }

    // Visit first node
    unordered_map<Node*, Node*> visited = {{node, new Node(node->val)}};
    queue<Node*> nodes;
    nodes.push(node);

    while (!nodes.empty()) {
      int size = nodes.size();
      while (size-- > 0) {
        Node* p = nodes.front();
        nodes.pop();
        for (auto* n : p->neighbors) {
          auto it = visited.find(n);
          if (it == visited.end()) {
            Node* clone = new Node(n->val);
            visited[n] = clone;
            visited[p]->neighbors.push_back(clone);
            nodes.push(n);
          } else {
            visited[p]->neighbors.push_back(it->second);
          }
        }
      }
    }
    return visited[node];
  }
};