一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 997|回复: 2
收起左侧

[Leetcode] Clone Graph 问题出错(Output Limit Exceeded)

[复制链接] |试试Instant~ |关注本帖
fangl086 发表于 2014-8-11 16:50:48 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
用dfs写的,debug了半天,找不出问题,找版上大牛求助!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;

  4. struct UndirectedGraphNode {
  5.         int label;
  6.         vector<UndirectedGraphNode *> neighbors;
  7.         UndirectedGraphNode(int x) : label(x) {};
  8. };


  9. class Solution {
  10. public:
  11.         UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
  12.                 if (node == NULL) return NULL;
  13.                 UndirectedGraphNode *head = new UndirectedGraphNode(node->label);
  14.                 dfs(node, head);
  15.                 return head;
  16.         }
  17.         void dfs(UndirectedGraphNode *node, UndirectedGraphNode *copy) {
  18.                 if ( !is_visited(node) ) {
  19.                         visited.push_back(node->label);       
  20.                         //cout << node->label << endl;
  21.                         vector<UndirectedGraphNode *> vec = node->neighbors;
  22.                         for (int i=0; i<vec.size(); i++) {
  23.                                 UndirectedGraphNode *n = new UndirectedGraphNode(vec[i]->label);
  24.                                 copy->neighbors.push_back(n);
  25.                                 //cout << n->label << ": " << vec[i]->label << endl;  
  26.                                 dfs(vec[i], n);
  27.                         }
  28.                 }       
  29.         }
  30.         bool is_visited(UndirectedGraphNode *node) {
  31.                 for (int i=0; i<visited.size(); i++) {
  32.                         if (visited[i] == node->label) return true;
  33.                 }
  34.                 return false;
  35.         }       
  36. private:
  37.         vector<int> visited;
  38. };

  39.         vector<int> visited;
  40.         bool is_visited(UndirectedGraphNode *node) {
  41.                 for (int i=0; i<visited.size(); i++) {
  42.                         if (visited[i] == node->label) return true;
  43.                 }
  44.                 return false;
  45.         }
  46.         void dfs(UndirectedGraphNode *node) {
  47.                 if ( !is_visited(node) ) {
  48.                         visited.push_back(node->label);       
  49.                         //cout << node->label << endl;
  50.                         vector<UndirectedGraphNode *> vec = node->neighbors;
  51.                         for (int i=0; i<vec.size(); i++) {
  52.                                 cout << node->label << "->neighbors: " << vec[i]->label << endl;  
  53.                                 dfs(vec[i]);
  54.                         }
  55.                 }       
  56.         }

  57.        

  58. int main()
  59. {
  60.         UndirectedGraphNode *node0 = new UndirectedGraphNode(0);
  61.         UndirectedGraphNode *node1 = new UndirectedGraphNode(1);
  62.         UndirectedGraphNode *node2 = new UndirectedGraphNode(2);
  63.        
  64.         node0->neighbors.push_back(node1);
  65.         node0->neighbors.push_back(node2);
  66.         node0->neighbors.push_back(node0);
  67.         node0->neighbors.push_back(node0);

  68.         node1->neighbors.push_back(node0);
  69.         node1->neighbors.push_back(node2);

  70.         node2->neighbors.push_back(node0);
  71.         node2->neighbors.push_back(node1);

  72.         Solution s;
  73.         UndirectedGraphNode *n = s.cloneGraph(node0);
  74.         //cout << n->neighbors[0]->label << endl;
  75.         //cout << n->neighbors[1]->label << endl;
  76.         //cout << n->neighbors.size() << endl;
  77.         dfs(n);
  78. }
复制代码
 楼主| fangl086 发表于 2014-8-11 19:43:17 | 显示全部楼层
  1. class Solution {
  2. public:
  3.         UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
  4.                 if (node == NULL) return node;
  5.                 unordered_map<int, UndirectedGraphNode *> visited;
  6.                 return dfs(node, visited);
  7.         }
  8.         UndirectedGraphNode *dfs(UndirectedGraphNode *node, unordered_map<int,
  9.                                                                 UndirectedGraphNode *> &visited) {
  10.                 UndirectedGraphNode *copy = new UndirectedGraphNode(node->label);
  11.                 if (visited.find(node->label) != visited.end())
  12.                         return visited[node->label];
  13.                        
  14.                 visited[node->label] = copy;       
  15.                 vector<UndirectedGraphNode *> vec = node->neighbors;
  16.                 for (int i=0; i<vec.size(); i++) {
  17.                         copy->neighbors.push_back(dfs(vec[i], visited));
  18.                 }
  19.                 return copy;
  20.         }
  21. };
复制代码
找不出问题,放上AC的代码吧
奇怪的是将 return visited[node->label];  改为 return copy;
错误提示:Output Limit Exceeded

很奇怪的问题,先放在这里了。
回复 支持 反对

使用道具 举报

 楼主| fangl086 发表于 2014-8-14 12:18:23 | 显示全部楼层
我在想是不是可能内存超出了预期
有知道的,回复下,不要沉了。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 04:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表