# Leetcode: Clone Graph

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 node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (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)
{
if (node == nullptr)    return nullptr;

// map的key为原始节点，value为拷贝的节点
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> copyMap;
// 完成给定节点的图的拷贝工作
clone(node, copyMap);

return copyMap[node];
}
private:
static UndirectedGraphNode* clone(UndirectedGraphNode* node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> &copyMap)
{
// 如果该节点已经拷贝过，直接返回该节点的拷贝
if (copyMap.find(node) != copyMap.end())  return copyMap[node];

// 否则，拷贝该节点及其相邻节点
UndirectedGraphNode* copiedNode = new UndirectedGraphNode(node->label);
copyMap[node] = copiedNode;
for (auto neighborNode : node->neighbors)
copiedNode->neighbors.push_back(clone(neighborNode, copyMap));

return copiedNode;
}
};```

0 条评论

• ### DOM4J使用过程中的一个细节问题：节点的选择

Node的selectNodes或者selectSingleNode方法，或者XPath的selectNodes或者selectSingleNode方法。

• ### 二叉树的遍历以及遇到的一些问题

这里以二叉树的前序遍历为例。输入前序遍历的数据元素（以空格作为空元素），构造二叉树，然后遍历二叉树输出每个数据元素所在的层。

• ### Leetcode: Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return t...

• ### BinarySearchTree二叉搜索树

二叉树具有唯一的根节点 二叉树每个节点最多有两个孩子 二叉树每个节点最多有一个父亲节点，根节点是唯一没有父亲节点的。 二叉树具有天然递归结构。 每个节点...

• ### openshift/origin工作记录（5）——node节点系统资源预留

解决思路为设置node节点系统资源预留值。

• ### openshift/origin工作记录（5）——node节点系统资源预留

实际应用中发现，如果不做处理，当集群内应用数量不断增加时，会占满node节点的系统资源，导致某node节点挂掉，同时也会造成openshift集群的卡死。

• ### 深入理解AbstractQueuedSynchronizer

JUC中的许多并发工具类ReentrantLock，CountDownLatch等的实现都依赖AbstractQueuedSynchronizer