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 node0
to both nodes1
and2
. - Second node is labeled as
1
. Connect node1
to node2
. - Third node is labeled as
2
. Connect node2
to node2
(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / \ / \ 0 --- 2 / \ \_/
/* Definition for undirected graph.
* struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { public: 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; } unordered_map<int, UndirectedGraphNode *> visited; unordered_set<int> completed; queue<UndirectedGraphNode *> uncompleted; uncompleted.push(node); int start_node_label = node->label; while (!uncompleted.empty()) { UndirectedGraphNode *curr = uncompleted.front(); uncompleted.pop(); if(completed.find(curr->label) == completed.end()) { UndirectedGraphNode *copy; if (visited.find(curr->label) == visited.end()) { copy = new UndirectedGraphNode(curr->label); visited.insert(make_pair(copy->label, copy)); } else { copy = visited[curr->label]; } for (UndirectedGraphNode *temp : curr->neighbors) { if (visited.find(temp->label) != visited.end()) { copy->neighbors.push_back(visited[temp->label]); } else { UndirectedGraphNode *neighbor = new UndirectedGraphNode(temp->label); copy->neighbors.push_back(neighbor); visited.insert(make_pair(neighbor->label, neighbor)); } } completed.insert(copy->label); for (UndirectedGraphNode *temp : curr->neighbors) { if (completed.find(temp->label) == completed.end()) { uncompleted.push(temp); } } } } return visited[start_node_label]; } };
No comments:
Post a Comment