Clone an undirected graph. Each node in the graph contains alabel
and
a list of itsneighbors
.
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
/ \
\_/
这里使用深度优先搜索。这样可以递归实现,如果是宽度优先,就要额外使用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;
}
};
//2014-2-18 update
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node)
{
unordered_map<int, UndirectedGraphNode *> ump_iu;
return clone(node, ump_iu);
}
UndirectedGraphNode *clone(UndirectedGraphNode *n,
unordered_map<int, UndirectedGraphNode *> &ump_iu)
{
if (!n) return n;
if (ump_iu.count(n->label)) return ump_iu[n->label];
UndirectedGraphNode *rs = new UndirectedGraphNode(n->label);
ump_iu[n->label] = rs;
for (int i = 0; i < n->neighbors.size(); i++)
{
(rs->neighbors).push_back(clone((n->neighbors[i]), ump_iu));
}
return rs;
}
分享到:
相关推荐
leetcode CloneGraph java 源代码
133.Clone_Graph_克隆图【LeetCode单题讲解系列】
用java解决包含但不限于array/tree/graph等几种数据结构、分治/DP/backtrack等几种算法思想的题目,并取得平均题解runtime beats 80%的成绩。 每天打卡(估计很快失败)平均每天1题保本,2题赚翻。 项目构建: 根...
leetcode 分类 Leetcode 介绍 leetcode个人题解,根据leetcode给的标签进行分类,按照数据结构对题目...graph:图论 greedy:贪心算法 recursion:递归算法 sort:排序算法 heap: 堆的应用题解 安装教程 clone IDEA JDK 8
Clone Graph, medium --- 类似于#138 207,课程表,中等 210 课程表 II,中等 261,图有效树,中等 310,最小高度树,中等 323,无向图中连通分量的数量,中等 444,序列重建,中 第二周——堆 215,数组中的第 K 个...
与大家分享我学习算法的一些经历。这个项目不定期更新。数组/链表:树相关:AVLTree 平衡二叉搜索树...BFSGraph 图BFS模板Dijkstra 寻求最短路SwimmingCrossSea 漂洋过海CloneGraph (leetcode 133)字符串相关:Reve
图形**** ****BFS class Solution { public Node cloneGraph ( Node node ) { if (node == null ) { return null ; } Map< Node> map = new HashMap<> (); Queue< Node> queue = new LinkedList<> (); queue ....
Clone_Graph 组合_总和 Counting_Carry_Digits 平等的 First_Missing_Positive Generate_All_Parenthesis_2 实现_StrStr Largest_Distance_Between_Nodes_Of_A_Tree Largest_Rectangle_In_Histogram Least_C
Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of 1 Bits Gray Code Single Number Single Number II Single Number III Power of Two Missing Number Maximum Product of Word Lengths Bitwise ...
存储库会定期更新,因此请确保提取代码git pull组织这些问题按其来源的主要主题划分问题陈述在代码顶部被注释掉LeetCode问题被命名为leetcode_(问题编号)_(问题标题),并且仅提供Solution类其他问题仅通过标题...