Clone an undirected graph. Each node in the graph contains a
label and a list of its neighbors.OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph
{0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by
#.- First node is labeled as
0. Connect node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
Solution:
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
void cloneHelper(UndirectedGraphNode *node, UndirectedGraphNode **clone,
map< int, UndirectedGraphNode *>& mp) {
if (node == NULL) {
return;
}
if (mp[node -> label]) {
*clone = mp[node -> label];
return;
}
*clone = new UndirectedGraphNode(node -> label);
mp[node -> label] = *clone;
int neighbors_size = node -> neighbors.size();
if (neighbors_size != 0) {
(*clone) -> neighbors = vector<UndirectedGraphNode *>(neighbors_size, NULL);
for (int i = 0; i < neighbors_size; i++) {
cloneHelper(node -> neighbors[i], &((*clone) -> neighbors[i]), mp);
}
}
return;
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == NULL) {
return NULL;
}
map<int, UndirectedGraphNode *> mp;
UndirectedGraphNode *clone = NULL;
cloneHelper(node, &clone, mp);
return clone;
}
};
===== Another one ========
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */class Solution {public: UndirectedGraphNode* dfs(UndirectedGraphNode *v, map<int, UndirectedGraphNode*> &visited){ UndirectedGraphNode* res = new UndirectedGraphNode(v->label); visited[v->label]=res; for (int i=0;i<v->neighbors.size();i++){ if (!visited[v->neighbors[i]->label]){ res->neighbors.push_back(dfs(v->neighbors[i],visited)); }else{ res->neighbors.push_back(visited[v->neighbors[i]->label]); } } return res; } UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if (node==NULL){ return NULL; }else{ map<int, UndirectedGraphNode*> visited; UndirectedGraphNode* res = dfs(node, visited); return res; } }};
================= Another attempt ==========/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node *cloneGraph(Node *node) {
unordered_map<int, Node *> mp;
return cloneHelper(node, mp);
}
Node *cloneHelper(Node *node, unordered_map< int, Node *>& mp) {
if (node == NULL) {
return NULL;
}
if (mp[node -> val]) {
return mp[node -> val];
}
Node *clone = new Node(node -> val);
mp[node -> val] = clone;
int neighbors_size = node -> neighbors.size();
if (neighbors_size != 0) {
clone -> neighbors = vector<Node *>(neighbors_size, NULL);
for (int i = 0; i < neighbors_size; i++) {
clone -> neighbors[i] = cloneHelper(node -> neighbors[i], mp);
}
}
return clone;
}
};
============= Few other =========class Solution { public: Node* cloneGraph(Node* node) { unordered_map<Node*, Node*> m; return helper(node, m); } Node* helper(Node* node, unordered_map<Node*, Node*>& m) { if (!node) return NULL; if (m.count(node)) return m[node]; Node *clone = new Node(node->val); m[node] = clone; for (Node *neighbor : node->neighbors) { clone->neighbors.push_back(helper(neighbor, m)); } return clone; } };
=========================
class Solution {
public: Node* cloneGraph(Node* node) { if (!node) return NULL; unordered_map<Node*, Node*> m; queue<Node*> q{{node}}; Node *clone = new Node(node->val); m[node] = clone; while (!q.empty()) { Node *t = q.front(); q.pop(); for (Node *neighbor : t->neighbors) { if (!m.count(neighbor)) { m[neighbor] = new Node(neighbor->val); q.push(neighbor); } m[t]->neighbors.push_back(m[neighbor]); } } return clone; } };
====================
/*
// Definition for a Node.
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 {
public:
Node* cloneGraph(Node* node) {
map<int, Node*> visited;
Node* ret;
helper(node, ret, visited);
return ret;
}
void helper(Node* node, Node*& copy, map<int, Node*>& visited) {
if (node == NULL) {
copy = NULL;
return;
}
if (visited.count(node->val)) {
copy = visited[node->val];
return;
}
copy = new Node(node -> val);
visited[node -> val] = copy;
for (auto neigh : node -> neighbors) {
Node *neighCopy;
helper(neigh, neighCopy, visited);
if (neighCopy != NULL) {
copy->neighbors.push_back(neighCopy);
}
}
return;
}
};
=============
/*
// Definition for a Node.
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 {
public:
Node* cloneGraph(Node* node) {
Node *clonedNode = NULL;
map<int, Node*> mp;
helper(node, clonedNode, mp);
return clonedNode;
}
void helper(Node* node, Node*& clonedNode, map<int, Node*>& mp) {
if (node == NULL) {
return;
}
if (mp.count(node -> val)) {
clonedNode = mp[node -> val];
return;
}
clonedNode = new Node(node -> val);
mp[node -> val] = clonedNode;
for (auto neighbor : node -> neighbors) {
Node* nodeNeighbor = NULL;
helper(neighbor, nodeNeighbor, mp);
clonedNode -> neighbors.push_back(nodeNeighbor);
}
}
};
===========/*
// Definition for a Node.
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 {
public:
Node* cloneGraph(Node* node) {
unordered_map<Node*, Node*> mp;
return helper(node, mp);
}
Node* helper(Node* node, unordered_map<Node*, Node*>& mp) {
if (node == NULL) {
return NULL;
}
if (mp.count(node) != 0) {
return mp[node];
}
Node* new_node = new Node(node -> val);
mp[node] = new_node;
// Add neighbors.
for (auto neighbor: node -> neighbors) {
new_node -> neighbors.push_back(helper(neighbor, mp));
}
return new_node;
}
};
No comments:
Post a Comment