Use a hash map to associate each original node with its clone so you never duplicate a node.

Clone Graph

medium

Acceptance: 50%

GraphsBFSDFS

Given a node in a connected undirected graph, produce a deep copy of the entire graph. Each node holds an integer value and a list of references to its neighbor nodes. The copied graph must have entirely new node objects with the same structure.

Examples

Example 1:

Input:adjList = [[2,3],[1,4],[1,4],[2,3]]

Output:[[2,3],[1,4],[1,4],[2,3]]

Explanation: A 4-node graph is cloned. Node 1 neighbors are 2 and 3; node 2 neighbors are 1 and 4; etc.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Clone Graph

Examples

Hints

Related Problems