</>Ali · LeetCode
#0133·MediumGraphs

Clone Graph

LeetCode #133 · Medium · Graphs · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

DFS with Hash Map

Strategy

  1. 1Use a hash map to track original node -> cloned node mapping.
  2. 2For each node, create a clone and add it to the map.
  3. 3Recursively clone all neighbors.
  4. 4If a neighbor is already cloned (in map), use the existing clone.
Time
O(V + E)
visit each node and edge once
Space
O(V)
the hash map and recursion stack
Problem description(from LeetCode)

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list of its neighbors.

Examples

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

Constraints

  • •The number of nodes in the graph is in the range [0, 100].
  • •1 <= Node.val <= 100
  • •Node.val is unique for each node.
  • •There are no repeated edges and no self-loops in the graph.
  • •The Graph is connected and all nodes can be visited starting from the given node.

C++ Solution

solution.cpp
class Solution {
public:
Node *cloneGraph(Node *node) {
    if (node == nullptr) return nullptr;
    unordered_map<Node *, Node *> m;
    return cloneGraph(node, m);
  }

  Node *cloneGraph(Node *node, unordered_map<Node *, Node *> &m) {
    Node *clone = new Node(node->val);
    m[node] = clone;
    for (auto neighbor : node->neighbors) {
      if (m[neighbor]) clone->neighbors.push_back(m[neighbor]);
      else clone->neighbors.push_back(cloneGraph(neighbor, m));
    }
    return clone;
  }
};

More Graphs problems