## Clone graph | Leetcode #133

CLONE GRAPH is a very important and interesting programming interview problem which is to create a clone for the given graph.This is a typical recursion programming interview problem which can be solved using DFS/BFS.I have explained how to solve this problem using DFS by using proper examples and intuitions.Simple DFS won’t work in this case.We need a MAP as well.I have shown the algorithm using an example and i have shown the code walk through at the end

```/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;

Node() {
val = 0;
neighbors = vector<Node*>();
}

Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}

Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/

class Solution {
void dfs(Node* curr,Node* node,vector<Node *>& visited)
{
//Node* copy = new Node(node->val);
visited[node->val] = node;
for(auto ele: curr->neighbors)
{
if(visited[ele->val] == NULL)
{
Node *newnode = new Node(ele->val);
(node->neighbors).push_back(newnode);
dfs(ele,newnode,visited);
}
else
(node->neighbors).push_back(visited[ele->val]);
}
}
public:
Node* cloneGraph(Node* node) {
if(node==NULL)
return NULL;

vector<Node *> visited(1000,NULL);
Node* copy = new Node(node->val);
visited[node->val] = copy;
//Iterate for all neighbors
for(auto curr: node->neighbors)
{
if(visited[curr->val] == NULL)
{
Node *newnode = new Node(curr->val);
(copy->neighbors).push_back(newnode);
dfs(curr,newnode,visited);
}
else
(copy->neighbors).push_back(visited[curr->val]);
}
return copy;
}
};

static int fastio = []() {
//#define endl '\n'
std::ios::sync_with_stdio(false);
//std::cin.tie(NULL);
//std::cout.tie(0);
return 0;
}();```