Skip to main content

Clone Graph

Problem​

Given a 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 (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

 

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    map<Node*, Node*> nodes;
    map<Node*, int> vis;

    void traverse(Node* root) {
        if (vis.find(root) != vis.end()) return;
        vis[root] = 1;
        Node* newNode = new Node(root->val);
        nodes[root] = newNode;
        for (auto nbr : root->neighbors) {
            traverse(nbr);
        }
    }

    Node* cloneGraph(Node* node) {
        if (!node) return NULL;
        traverse(node);
        for (auto nde : nodes) {
            for (auto nbr : nde.first->neighbors) {
                nde.second->neighbors.push_back(nodes[nbr]);
            }
        }
        return nodes[node];
    }
};