Clone Graph

Problem

Given a node in a connected undirected graph, return a deep copy of the graph.

Each node in the graph contains an integer value and a list of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

The graph is shown in the test cases as an adjacency list. An adjacency list is a mapping of nodes to lists, used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

For simplicity, nodes values are numbered from 1 to n, where n is the total number of nodes in the graph. The index of each node within the adjacency list is the same as the node’s value (1-indexed).

The input node will always be the first node in the graph and have 1 as the value.

Examples

Example 1:

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

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

Example 2:

Input: adjList = [[]]

Output: [[]]

Example 3:

Input: adjList = []

Output: []

Constraints

• 0 <= The number of nodes in the graph <= 100.
• 1 <= Node.val <= 100
• There are no duplicate edges and no self-loops in the graph.

You should aim for a solution with O(V + E) time and O(V) space, where V is the number of vertices and E is the number of edges in the given graph.

Solution

Use open list to search over the graph. We track old to new mappings of nodes. Every iteration removes from open, generates children, if unseen we create a node and to open, and always make the edge.

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
 
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) { return nullptr; }
        std::queue<Node*> open;
        std::unordered_map<Node*, Node*> old_to_new;
 
        // Init search
        old_to_new[node] = new Node(node->val);
        open.push(node); 
        while (!open.empty()) {
            Node *current = open.front();
            open.pop();
            for (const auto &neighbor : current->neighbors) {
                // Unseed node, add to queue
                if (!old_to_new.contains(neighbor)) {
                    old_to_new[neighbor] = new Node(neighbor->val);
                    open.push(neighbor);
                }
                // Link graph
                old_to_new[current]->neighbors.push_back(old_to_new[neighbor]);
            }
        }
        return old_to_new[node];
    }
};