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
/ \_/
这里使用深度优先搜索。这样可以递归实现，如果是宽度优先，就要额外使用queue容器。
关键点：
1 这里的clone需要深度拷贝，就是要使用new操作了
2 防止回路无限循环，就要使用hash表，这里使用unordered_map记录访问过的节点。因为这里的label应该是唯一的才对，所以可以直接使用label作为关键字就可以。
看起来挺难的，因为图总给人困难的感觉，其实不难，3到4星级难度吧，很多都是基本操作组合起来。我一次性通过了。
struct UndirectedGraphNode
{
int label;
vector<UndirectedGraphNode *> neighbors;
UndirectedGraphNode(int x) : label(x) {};
};
class Solution
{
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node)
{
unordered_map<int, UndirectedGraphNode *> track;
return cloneGraph(node, track);
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node, unordered_map<int, UndirectedGraphNode *> &track)
{
if (!node) return NULL;
if (track.count(node->label)) return track[node->label];
UndirectedGraphNode *new_node = new UndirectedGraphNode(node->label);
new_node->neighbors.resize(node->neighbors.size());
track[node->label] = new_node;
for (int i = 0; i < node->neighbors.size(); i++)
{
new_node->neighbors[i] = cloneGraph(node->neighbors[i], track);
}
return new_node;
}
};