Scribd
Upload
196 views

Clone Graph - LeetCode

This document provides a problem to clone an undirected graph. The graph is represented as a reference to one of the graph nodes. Each node contains a value and a list of neighboring nodes. The task is to return a deep copy of the entire graph using the reference to the starting node. The graph will contain between 1 and 100 nodes without repeated edges or self loops.

Uploaded by

jon monroe
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
196 views

Clone Graph - LeetCode

This document provides a problem to clone an undirected graph. The graph is represented as a reference to one of the graph nodes. Each node contains a value and a list of neighboring nodes. The task is to return a deep copy of the entire graph using the reference to the starting node. The graph will contain between 1 and 100 nodes without repeated edges or self loops.

Uploaded by

jon monroe
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

9/27/2019 (2) Clone Graph - LeetCode

. Clone Graph C++ 


Medium 969 1022 Favorite Share 1▾ /*
2 // Definition
3 class Node {
Given a reference of a node in a connected undirected graph, return a deep copy 4 public:
5 int val;
(clone) of the graph. Each node in the graph contains a val ( int ) and a list 6 vector<Nod
( List[Node] ) of its neighbors. 7
8 Node() {}
9
 
10 Node(int _
_neighbors) {
Example: 11 val =
12 neighb
13 }
14 };
15 */
16 ▾ class Solution
17 public:
18 ▾ Node* clon
{
19
20 }
21 };

Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},
{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":
[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},
{"$ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

1. The number of nodes will be between 1 and 100.


2. The undirected graph is a simple graph, which means no repeated edges
and no self-loops in the graph.
3. Since the graph is undirected, if node p has node q as neighbor, then node
q must have node p as neighbor too.
4. You must return the copy of the given node as a reference to the cloned
graph.

Accepted 246,117 Submissions 858,856

Console Contribute
Seen this question in a real interview before? Yes No

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

You might also like