求帮忙看看这个clone graph的解法。弄半天还是不对。多谢！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求帮忙看看这个clone graph的解法。弄半天还是不对。多谢！

求帮忙看看这个clone graph的解法。弄半天还是不对。多谢！# JobHunting - 待字闺中

t*r2014-12-17 08:12

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*n2014-12-17 08:12

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*d2014-12-17 08:12

3 楼

graphCopy->neighbors.push_back(DFS(node,mp));
这句node 改 neighbor

C*e2014-12-17 08:12

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);
}
}