Description:
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 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:
Time Complexity : O(n)
Space Complexity: O(n)
// DFS approachvarcloneGraph=function(node){// Nodes we have already copiedconstvisited={};// DFS function to copy graphconstdfs=(node)=>{if(!node)returnnode;// If we have seen this node before, return itif(visited[node.val]!=null)returnvisited[node.val];// Create base for copied nodeconstroot=newNode(node.val);// Add this copied node to group of nodes we hav copiedvisited[node.val]=root;// Add copied neighbors to the current copied nodenode.neighbors.forEach(n=>root.neighbors.push(dfs(n)))returnroot;}// Return new copied graphreturndfs(node);};
Top comments(1)

I found that solution is very popular and helpful:youtu.be/t9pj1Ail2z4
For further actions, you may consider blocking this person and/orreporting abuse