[Algo] 132. Deep Copy Undirected Graph

/*
* class GraphNode {
*   public int key;
*   public List<GraphNode> neighbors;
*   public GraphNode(int key) {
*     this.key = key;
*     this.neighbors = new ArrayList<GraphNode>();
*   }
* }
*/
public class Solution {
  public List<GraphNode> copy(List<GraphNode> graph) {
    // Write your solution here.
    Map<GraphNode, GraphNode> map = new HashMap<>();
    for (GraphNode node : graph) {
      if (!map.containsKey(node)) {
        map.put(node, new GraphNode(node.key));
      }
      dfs(node, map);
    }
    return new ArrayList<>(map.values());
  }

  private void dfs(GraphNode node, Map<GraphNode, GraphNode> map) {
    GraphNode newNode = map.get(node);
    for (GraphNode gNode : node.neighbors) {
      if (!map.containsKey(gNode)) {
        map.put(gNode, new GraphNode(gNode.key));
      }
      newNode.neighbors.add(map.get(gNode));
    }
  }
}