leetcode || 133、Clone Graph
3574 ワード
problem:
Clone an undirected graph. Each node in the graph contains a
OJ's undirected graph serialization:
Nodes are labeled uniquely. We use
As an example, consider the serialized graph
The graph has a total of three nodes, and therefore contains three parts as separated by
First node is labeled as
Second node is labeled as
Third node is labeled as
Visually, the graph looks like the following:
Hide Tags
Depth-first Search Breadth-first Search Graph
标题:図のコピー(構造とデータは変わらず、ノードを新規作成する)
thinking:
(1)図の各ノードを新規作成し,隣接関係を維持する.
(2)unordered_の採用mapは、元のノードと新しいノードを格納します.unorderedではなくmap,効率はかなり高い
(3)BFS思想を用いて,元ノードの隣接ノードをすべてスタックまたはスタックに入れ,ノードを遍歴する.
(4)mapでkeyが存在するかどうかfind()を呼び出すかcount()を呼び出すことができ,後者はより効率的である.
(5)提出に失敗し、結果が正しくない:
Input:{0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}
Output:{0,5,1#1,5,2#2,3#3,4,4#4,5,5#5}
Expected:{0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}
実際には,無方向図ではノードの出現順序が図の構造に影響しないため,この検証プログラムは1つの結果しか検証していないとしか言いようがない.
code:
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
/ \
\_/
Hide Tags
Depth-first Search Breadth-first Search Graph
标题:図のコピー(構造とデータは変わらず、ノードを新規作成する)
thinking:
(1)図の各ノードを新規作成し,隣接関係を維持する.
(2)unordered_の採用map
(3)BFS思想を用いて,元ノードの隣接ノードをすべてスタックまたはスタックに入れ,ノードを遍歴する.
(4)mapでkeyが存在するかどうかfind()を呼び出すかcount()を呼び出すことができ,後者はより効率的である.
(5)提出に失敗し、結果が正しくない:
Input:{0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}
Output:{0,5,1#1,5,2#2,3#3,4,4#4,5,5#5}
Expected:{0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}
実際には,無方向図ではノードの出現順序が図の構造に影響しないため,この検証プログラムは1つの結果しか検証していないとしか言いようがない.
code:
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> record;
if(node == NULL)
return node;
stack<UndirectedGraphNode*> queue;
queue.push(node);
while(!queue.empty()) {
UndirectedGraphNode *nextNode = queue.top();
queue.pop();
if(!record.count(nextNode)) {
UndirectedGraphNode *newNode = new UndirectedGraphNode(nextNode->label);
record[nextNode] = newNode;
}
for(int i = nextNode->neighbors.size()-1; i >= 0 ; i --) {
UndirectedGraphNode *childNode = nextNode->neighbors[i];
if(!record.count(childNode)) {
UndirectedGraphNode *newNode = new UndirectedGraphNode(childNode->label);
record[childNode] = newNode;
queue.push(childNode);
}
record[nextNode]->neighbors.push_back(record[childNode]);
}
}
return record[node];
}
};