Leetcode Clone Graph problem solution YASH PAL, 31 July 2024 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) seen.add(id(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++){ val.neighbors.add(res.get(key.neighbors.get(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; } coding problems