Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label
(int
) and a list (List[UndirectedGraphNode]
) of its neighbors
. There is an edge between the given node and each of the nodes in its neighbors.
OJ’s undirected graph serialization (so you can understand error output):
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 / \ \_/
Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.
Solution: Queue + Hashtable
Time complexity: O(V+E)
Space complexity: O(V+E)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua, 44ms, 16.8MB class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return nullptr; typedef UndirectedGraphNode Node; unordered_set<Node*> done; unordered_map<Node*, Node*> m; queue<Node*> q; q.push(node); while (!q.empty()) { Node* s = q.front(); q.pop(); if (done.count(s)) continue; done.insert(s); if (!m.count(s)) m[s] = new Node(s->label); Node* t = m[s]; for (Node* ss : s->neighbors) { if (!m.count(ss)) m[ss] = new Node(ss->label); q.push(ss); t->neighbors.push_back(m[ss]); } } return m[node]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment