Leetcode Clone Graph problem solution

In this Leetcode Clone Graph problem solution, we have given a node reference in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {

public int val;

public List<Node> neighbors;

}

Problem solution in Python.

```from collections import deque
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
new_root = Node(node.val, [])
self.rBfs(deque([node]), set([id(node)]), {id(node): new_root})
return new_root

def rBfs(self, deq, seen, lut):
for i in range(len(deq)):
new_val = lut[id(deq[0])]
for j in deq[0].neighbors:
if id(j) not in lut:
lut[id(j)] = Node(j.val, [])
new_val.neighbors.append(lut[id(j)])
if id(j) not in seen:
deq.append(j)
deq.popleft()
if deq: self.rBfs(deq, seen, lut)
```

Problem solution in Java.

```class Solution {
Map<Node,Node> res = new HashMap<>();
public Node cloneGraph(Node node) {
if(node == null) return null;
dfs(node);
createCopy();
return res.get(node);
}
void createCopy() {
for(Map.Entry<Node,Node> kk : res.entrySet()) {
Node val = kk.getValue();
Node key = kk.getKey();
for(int i=0;i<key.neighbors.size();i++){
}
}
}
void dfs(Node node) {
res.put(node,new Node(node.val));
for(int i=0;i<node.neighbors.size();i++) {
if(!res.containsKey(node.neighbors.get(i))) {
dfs(node.neighbors.get(i));
}
}
}
}
```

Problem solution in C++.

```class Solution {
public:
Node* cloneGraph(Node* node) {
if(!node) return NULL;
unordered_map<Node*,Node*> cache;
unordered_set<Node*> visited;
return cloneGraph(node, cache, visited);
}

Node* cloneGraph(Node* node, unordered_map<Node*,Node*>& cache, unordered_set<Node*>&visited) {

if(visited.find(node) != visited.end()) return cache[node];

visited.insert(node);

if (cache.find(node) == cache.end()) {
Node* tmp = new Node(node->val);
cache[node] = tmp;
}

for(auto item : node->neighbors) {
cache[node]->neighbors.push_back(cloneGraph(item,cache,visited));

}
return cache[node];
}
};
```

Problem solution in C.

```static struct Node* dfsCopy(struct Node* s, struct Node** newNodes);
static struct Node* newNode(struct Node* original);

struct Node *cloneGraph(struct Node *s) {
struct Node* newGraph = NULL;
if (s != NULL) {
struct Node** newNodes = calloc(101, sizeof(struct Node*));
newGraph = dfsCopy(s, newNodes);
free(newNodes);
}
return newGraph;
}

static struct Node* dfsCopy(struct Node* s, struct Node** newNodes) {
int curr = s->val;
newNodes[curr] = newNode(s);
for (int i = 0; i < s->numNeighbors; i++) {
if (newNodes[s->neighbors[i]->val] == NULL) {
newNodes[curr]->neighbors[i] = dfsCopy(s->neighbors[i], newNodes);
} else {
newNodes[curr]->neighbors[i] = newNodes[s->neighbors[i]->val];
}
}
return newNodes[curr];
}

static struct Node* newNode(struct Node* original) {
struct Node* new = malloc(sizeof(*new));
new->val = original->val;
new->numNeighbors = original->numNeighbors;
new->neighbors = calloc(new->numNeighbors, sizeof(struct Node*));
return new;
}
```