Problem
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
/ \
\_/
Solution
/**
* Definition for undirected graph.
* function UndirectedGraphNode(label) {
* this.label = label;
* this.neighbors = []; // Array of UndirectedGraphNode
* }
*/
/**
* @param {UndirectedGraphNode} graph
* @return {UndirectedGraphNode}
*/
var cloneGraph = function(graph) {
return clone(graph, {});
};
var clone = function (node, map) {
if (!node) return null;
if (map[node.label]) return map[node.label];
var cloneNode = new UndirectedGraphNode(node.label);
map[node.label] = cloneNode;
for (var i = 0; i < node.neighbors.length; i++) {
cloneNode.neighbors.push(clone(node.neighbors[i], map));
}
return cloneNode;
};
Explain:
不用管描述里的 #
,
什么的,题意就是复制一个无向图,不要想复杂了。
注意有重复节点的话,存个引用就行,用哈希表判断是否重复。
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).