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&lt;Node&gt; neighbors;
}


&nbsp;

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.

&nbsp;
Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).


Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.


Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.


&nbsp;
Constraints:


	The number of nodes in the graph is in the range [0, 100].
	1 &lt;= Node.val &lt;= 100
	Node.val is unique for each node.
	There are no repeated edges and no self-loops in the graph.
	The Graph is connected and all nodes can be visited starting from the given node.


    def cloneGraph(self, node: 'Node') -> 'Node':
        
        if node == None:
            return None
        
        new_node = Node(node.val, [])
        
        visited = set()
        
        q = [[node, new_node]]
        visited.add(node.val)
        
        adj_map = {}
        
        adj_map[node] = new_node
        
        while len(q) != 0:
            
            curr = q.pop(0)
            
            
            for n in curr[0].neighbors:
                
                # if n.val not in visited:
                if n not in adj_map and n is not None:
                    new = Node(n.val, [])
                    curr[1].neighbors.append(new)
                    adj_map[n] = new
                else:
                    curr[1].neighbors.append(adj_map[n])
                    
                if n.val not in visited:
                    q.append([n, adj_map[n]])
                    visited.add(n.val) 
        
        
        return new_node
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public void dfs(Node node , Node copy , Node[] visited){
        visited[copy.val] = copy;// store the current node at it's val index which will tell us that this node is now visited
        
//         now traverse for the adjacent nodes of root node
        for(Node n : node.neighbors){
//             check whether that node is visited or not
//              if it is not visited, there must be null
            if(visited[n.val] == null){
//                 so now if it not visited, create a new node
                Node newNode = new Node(n.val);
//                 add this node as the neighbor of the prev copied node
                copy.neighbors.add(newNode);
//                 make dfs call for this unvisited node to discover whether it's adjacent nodes are explored or not
                dfs(n , newNode , visited);
            }else{
//                 if that node is already visited, retrieve that node from visited array and add it as the adjacent node of prev copied node
//                 THIS IS THE POINT WHY WE USED NODE[] INSTEAD OF BOOLEAN[] ARRAY
                copy.neighbors.add(visited[n.val]);
            }
        }
        
    }
    public Node cloneGraph(Node node) {
        if(node == null) return null; // if the actual node is empty there is nothing to copy, so return null
        Node copy = new Node(node.val); // create a new node , with same value as the root node(given node)
        Node[] visited = new Node[101]; // in this question we will create an array of Node(not boolean) why ? , because i have to add all the adjacent nodes of particular vertex, whether it's visited or not, so in the Node[] initially null is stored, if that node is visited, we will store the respective node at the index, and can retrieve that easily.
        Arrays.fill(visited , null); // initially store null at all places
        dfs(node , copy , visited); // make a dfs call for traversing all the vertices of the root node
        return copy; // in the end return the copy node
    }
}
                                          'IF YOU LIKE IT THEN PLS UpVote😎😎😎'
class Solution {
    public:
    Node* dfs(Node* cur,unordered_map<Node*,Node*>& mp)
    {
        vector<Node*> neighbour;
        Node* clone=new Node(cur->val);
        mp[cur]=clone;
            for(auto it:cur->neighbors)
            {
                if(mp.find(it)!=mp.end())   //already clone and stored in map
                {
                    neighbour.push_back(mp[it]);    //directly push back the clone node from map to neigh
                }
                else
                    neighbour.push_back(dfs(it,mp));
            }
            clone->neighbors=neighbour;
            return clone;
    }
    Node* cloneGraph(Node* node) {
        unordered_map<Node*,Node*> mp;
        if(node==NULL)
            return NULL;
        if(node->neighbors.size()==0)   //if only one node present no neighbors
        {
            Node* clone= new Node(node->val);
            return clone; 
        }
        return dfs(node,mp);
    }
};
var cloneGraph = function(node) {
    if(!node)
        return node;
    
    let queue = [node];
    
    let map = new Map();
    
	//1. Create new Copy of each node and save in Map
    while(queue.length) {
        let nextQueue = [];
        
        for(let i = 0; i < queue.length; i++) {
            let n = queue[i];
            
            let newN = new Node(n.val);
            
            if(!map.has(n)) {
                map.set(n, newN);
            }
            
            let nei = n.neighbors;
            
            for(let j = 0; j < nei.length; j++) {
                if(map.has(nei[j]))
                    continue;
                nextQueue.push(nei[j]); 
            }
        }
        
        queue = nextQueue;
    }
    
    queue = [node];
    
    let seen = new Set();
    seen.add(node);
    
	//2. Run BFS again and populate neighbors in new node created in step 1.
    while(queue.length) {
        let nextQueue = [];
        
        for(let i = 0; i < queue.length; i++) {
            let n = queue[i];
            
            let nei = n.neighbors;
            let newn = map.get(n);
            
            for(let j = 0; j < nei.length; j++) {
                newn.neighbors.push(map.get(nei[j]));
                
                if(!seen.has(nei[j])) {
                    nextQueue.push(nei[j]); 
                    seen.add(nei[j]);
                }
            }
        }
        
        queue = nextQueue;
    }
    
    return map.get(node);
};
Clone Graph