LeetCode 133. Clone Graph

LeetCode 133. Clone Graph

LINK: https://leetcode.com/problems/clone-graph/

Matter

You are given a reference to a node in an undirected graph.

Create a deep copy of the entire graph and return the cloned node corresponding to the input.

Each node contains a value and a list of its neighbors.

Example.

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

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

Explanation:
Each node and its neighbors are duplicated to form an identical graph structure.

[2]
Input:
adjList = [[]]

Output:
[[]]

Explanation:
A single node with no neighbors.

[3]
Input:
adjList = []

Output:
[]

Explanation:
An empty graph.

Constraints

0 <= number of nodes <= 100

1 <= Node.val <= 100

Node values are unique

No duplicate edges and no self-loops

Problem analysis

This is a graph traversal + cloning problem.

The key difficulty is Avoid duplicating the same node multiple times

Since the graph may contain cycles, we must track already cloned nodes.

• Use a hashmap to store mapping:

original_node → cloned_node

Solution

#include <iostream>
#include <vector>
#include <functional>
#include <unordered_map>

class Node {
public:
    int val;
    std::vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = std::vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = std::vector<Node*>();
    }
    Node(int _val, std::vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};


class Solution {
public:
    Node* cloneGraph(Node* node) 
    {
        std::function<Node*(Node*)> lmdClone = [&](Node* nodeOrg) -> Node*
        {
            Node* nodeClone = nullptr;

            do
            {
                if(visited.find(nodeOrg) != visited.end())
                {
                    nodeClone = visited[nodeOrg];
                    break;
                }

                nodeClone = new Node(nodeOrg->val);
                nodeClone->neighbors.resize(nodeOrg->neighbors.size(), nullptr);
                
                visited[nodeOrg] = nodeClone;
                
                for(int i =0; i < nodeOrg->neighbors.size(); ++i) 
                {
                    if (nodeOrg->neighbors[i] == nullptr)
                        nodeClone->neighbors[i] = nullptr;
                    else
                        nodeClone->neighbors[i] = lmdClone(nodeOrg->neighbors[i]);
                }
            } 
            while (false);

            return nodeClone;
        };

        Node* nodeResult = nullptr;

        do
        {
            if (node == nullptr)
                break;

            nodeResult = lmdClone(node);
        } 
        while (false);

        return nodeResult;
    }
public:
    std::unordered_map<Node*, Node*> visited;
};