Solution to Clone Graph by LeetCode

Question: https://oj.leetcode.com/problems/clone-graph/

Question Name: Clone Graph

# Definition for a undirected graph node

# class UndirectedGraphNode:

# def __init__(self, x):

# self.label = x

# self.neighbors = []

class Solution:

# @param node, a undirected graph node

# @return a undirected graph node

def cloneGraph(self, node):

# Empty graph

if node == None: return

# Do the work in two rounds. In the first round, we clone all the

# new nodes only with label. And let their neighbors array empty.

# In the second round, we will assign the neighbors of cloned

# node with the reference to new cloned ones.

# Clone nodes only with label

cloned = {}

currentLayer = [node]

while len(currentLayer) != 0:

nextLayer = []

for toClone in currentLayer:

if toClone in cloned: continue

temp = UndirectedGraphNode(toClone.label)

nextLayer.extend(toClone.neighbors)

cloned[toClone] = temp

currentLayer = nextLayer

# Assign the neighbors of new cloned nodes.

for oldNode in cloned:

newNode = cloned[oldNode]

newNode.neighbors = [cloned[neighbor] for neighbor

in oldNode.neighbors]

return cloned[node]

Both BFS and DFS are given. Leetcode is not very stable recently. The new UIs never work right…

#include <vector>

#include <queue>

#include <unordered_map>

using namespace std;

namespace CloneGraph {

struct UndirectedGraphNode {

int label;

vector<UndirectedGraphNode*> neighbors;

UndirectedGraphNode(int x) : label(x) {};

};

class SolutionCloneGraph {

private:

UndirectedGraphNode* aux(unordered_map<int, UndirectedGraphNode*>& notes, UndirectedGraphNode* node) {

UndirectedGraphNode *newnode = nullptr, *neighbor = nullptr;

if (nullptr != node) {

auto end = notes.end();

newnode = new UndirectedGraphNode(node->label);

notes.emplace(newnode->label, newnode);

for (auto n : node->neighbors) {

if (end == notes.find(n->label)) neighbor = this->aux(notes, n);

else neighbor = notes.find(n->label)->second;

newnode->neighbors.push_back(neighbor);

}

return newnode;

}

public:

//BFS

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

UndirectedGraphNode *ans = nullptr, *current = nullptr, *neighbor = nullptr;

if (nullptr != node) {

unordered_map<int, UndirectedGraphNode*> notes;

auto nend = notes.end();

queue<UndirectedGraphNode*> q;

int size = 0;

ans = new UndirectedGraphNode(node->label);

ans->neighbors = node->neighbors;

q.push(ans);

notes.emplace(node->label, ans);

while (false == q.empty()) {

size = q.size();

for (int i = 0;i < size; ++i) {

current = q.front(); q.pop();

vector<UndirectedGraphNode *> vec;

for (auto n : current->neighbors) {

if (nend == notes.find(n->label))

{

neighbor = new UndirectedGraphNode(n->label);

neighbor->neighbors = n->neighbors;

q.push(neighbor);

notes.emplace(n->label, neighbor);

}

else

neighbor = notes.find(n->label)->second;

vec.push_back(neighbor);

}

current->neighbors = vec;

}

return ans;

}

//DFS

UndirectedGraphNode *cloneGraph1(UndirectedGraphNode *node) {

UndirectedGraphNode *ans = nullptr;

if (nullptr != node) {

unordered_map<int, UndirectedGraphNode*> notes;

ans = this->aux(notes, node);

}

return ans;

}

};

}

Solution to Clone Graph by LeetCode

One Reply to “Solution to Clone Graph by LeetCode”

Leave a Reply to micropentium6 Cancel reply