aboutsummaryrefslogtreecommitdiff
path: root/clone_graph.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'clone_graph.cpp')
-rw-r--r--clone_graph.cpp55
1 files changed, 0 insertions, 55 deletions
diff --git a/clone_graph.cpp b/clone_graph.cpp
deleted file mode 100644
index fc372a0..0000000
--- a/clone_graph.cpp
+++ /dev/null
@@ -1,55 +0,0 @@
-// 133. Clone Graph
-#include <cstddef>
-#include <unordered_map>
-#include <vector>
-using namespace std;
-
-// given reference of a node in a connected undirected graph. return a deep copy
-// (clone) of the graph. each node in the graph contains a value and a
-// list (list[node]).
-
-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;
- }
-};
-
-class Solution {
- Node *dfs(Node *curr, unordered_map<Node *, Node *> &um) {
- vector<Node *> neighbour;
- Node *clone = new Node(curr->val);
- um[curr] = clone;
- for (auto i : curr->neighbors) {
- if (um.find(i) != um.end())
- neighbour.push_back(um[i]);
- else
- neighbour.push_back(dfs(i, um));
- }
- clone->neighbors = neighbour;
- return clone;
- }
-
-public:
- Node *cloneGraph(Node *node) {
- unordered_map<Node *, Node *> um;
- if (node == NULL)
- return NULL;
- if (!node->neighbors.size()) {
- Node *clone = new Node(node->val);
- return clone;
- }
- return dfs(node, um);
- }
-};