/*

* 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));

    }

  }

}

/*

* 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 gNode: graph) {

      map.put(gNode, new GraphNode(gNode.key));

    }

    for (GraphNode node : graph) {

      GraphNode cpNode = map.get(node);

      for (GraphNode nei: node.neighbors) {

        cpNode.neighbors.add(map.get(nei));

      }

    }

    return new ArrayList<>(map.values());

  }

}