Classic 150 Interview Questions P133 Clone Graph

---

Timeline

Timeline

2025-11-03

init

BFS

---

Problem:

P133 Clone Graph

https://leetcode.cn/problems/clone-graph/solutions/370663/ke-long-tu-by-leetcode-solution/?envType=study-plan-v2&envId=top-interview-150

Using a hash table to map original nodes to cloned nodes, and then BFS populates the visited hash table while also populating the cloned nodes—that’s quite clever.

/*
// Definition for a Node.
*/
#include <vector>
#include <unordered_map>
#include <queue>

using std::queue;
using std::unordered_map;
using std::vector;

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 {
private:
	unordered_map<Node *, Node *> visited;

public:
	// Given a reference of a node in an undirected connected graph, return a deep copy (clone) of the graph.
	Node *cloneGraph(Node *node)
	{
		if (node == nullptr) {
			return nullptr;
		}

		unordered_map<Node *, Node *> visited;
		queue<Node *> q;
		Node *cur, *cloneNode;

		cloneNode = new Node(node->val);
		visited[node] = cloneNode;
		q.push(node);

		while (!q.empty()) {
			cur = q.front();
			q.pop();
			for (Node *neighbor : cur->neighbors) {
				if (visited.count(neighbor) == 0) { // Unvisited
				   	// Create the corresponding clone node for this node.
					visited[neighbor] = new Node(neighbor->val);
					q.push(neighbor);
				}
				// Add the newly created clone node or the already visited node to the neighbor list of the clone node corresponding to the node at the front of the queue.
				visited[cur]->neighbors.push_back(visited[neighbor]);
			}
		}

		return cloneNode;
	}
};