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)
                    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