t**r
发帖数: 3428 | 1 class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return NULL;
map mp;
return DFS(node, mp);
}
UndirectedGraphNode* DFS(UndirectedGraphNode* node, map<
UndirectedGraphNode*, UndirectedGraphNode*>& mp){
if(mp.find(node) != mp.end()) {
return mp[node];
}
UndirectedGraphNode* graphCopy = new UndirectedGraphNode(node->label
);
mp[node] = graphCopy;
for(auto neighbor: node->neighbors){
graphCopy->neighbors.push_back(DFS(node,mp));
}
return graphCopy;
}
};
Submission Result: Wrong Answer
Input: {-1,1#1}
Output: {-1,-1}
Expected: {-1,1#1} | d****n
发帖数: 233 | 2 把
for(auto neighbor: node->neighbors){
graphCopy->neighbors.push_back(DFS(node,mp));
}
改成
for(auto neighbor: node->neighbors){
graphCopy->neighbors.push_back(DFS(neighbor,mp));
}
另外，可以参考我的blog for the two ways to solve this problem:
http://codeanytime.blogspot.com/2014/11/clone-graph.html
【在 t**r 的大作中提到】
: class Solution {
: public:
: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
: if(!node) return NULL;
: map mp;
: return DFS(node, mp);
: }
: UndirectedGraphNode* DFS(UndirectedGraphNode* node, map<
: UndirectedGraphNode*, UndirectedGraphNode*>& mp){
: if(mp.find(node) != mp.end()) {
| h**d
发帖数: 630 | 3 graphCopy->neighbors.push_back(DFS(node,mp));
这句node 改 neighbor | C****e
发帖数: 27 | 4 我今天也正好在做这题，看的是网络答案，但是不知道main函数要怎么写才能实现调用
输出结果呢？
public class clonegraph {
public static void main(String[] args){
}
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node==null)
return null;
LinkedList queue = new LinkedList<
UndirectedGraphNode>();
HashMap map = new HashMap<
UndirectedGraphNode, UndirectedGraphNode>();
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
map.put(node,copy);
queue.offer(node);
while(!queue.isEmpty())
{
UndirectedGraphNode cur = queue.poll();
for(int i=0;i
{
if(!map.containsKey(cur.neighbors.get(i)))
{
copy = new UndirectedGraphNode(cur.neighbors.get(i).label);
map.put(cur.neighbors.get(i),copy);
queue.offer(cur.neighbors.get(i));
}
map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));
}
}
return map.get(node);
}
} |
|
