Graph: You are given a graph, clone the graph using deep copy

Problem Statement:

You are given a reference of a node in a connected undirected graph.

You need to return a deep copy of the graph.

Example:

Input:

1 ---- 2
|      |   
|      | 
|      | 
3 ---- 4

Output:

1 ---- 2
|      |   
|      | 
|      | 
3 ---- 4

Solution Explanation:

For the solution we will use DFS approach.

To create a deep copy, traverse the original graph and the nodes will be the key and the values will be corresponding nodes of the new graph.

We can take set to ensure that the same node is not visited twice.

Then traverse the original graph, for each node, create a copy and add it into the dictionary and recursively create copy of all of its neighbors.

To keep track of the visited nodes, take a visited set.

Time Complexity: O(N+E), N is the number of nodes. E is the edges in the graph.
Space Complexity: O(N+E),

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;


class Node 
{

public:
    int val;
    vector<Node*> neighbors;
};


Node* clone(Node* node, unordered_map<Node*, Node*>& nodeMap) 
{
    if (node == nullptr) 
    {
        return nullptr;
    }

    if (nodeMap.count(node) > 0) 
    {
        return nodeMap[node];
    }

    Node* cloneNode = new Node();
    cloneNode->val = node->val;
    nodeMap[node] = cloneNode;

    for (Node* neighbor : node->neighbors) 
    {
        cloneNode->neighbors.push_back(clone(neighbor, nodeMap));
    }
    return cloneNode;
}

Node* cloneGraph(Node* node) 
{
    if (node == nullptr) 
    {
        return nullptr;
    }

    unordered_map<Node*, Node*> nodeMap;
    return clone(node, nodeMap);
}

Node* buildGraph() 
{
    Node* node1 = new Node(); node1->val = 0;
    Node* node2 = new Node(); node2->val = 1;
    Node* node3 = new Node(); node3->val = 2;
    Node* node4 = new Node(); node4->val = 3;

    node1->neighbors = {node2, node3};
    node2->neighbors = {node1, node4};
    node3->neighbors = {node1, node4};
    node4->neighbors = {node3, node1};

    return node1;
}


int main() 
{
    Node* original = buildGraph();

    // Clone the graph
    Node* cloned = cloneGraph(original);

    return 0;
}