{"id":4844,"date":"2019-02-13T08:34:14","date_gmt":"2019-02-13T16:34:14","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4844"},"modified":"2019-02-13T08:40:27","modified_gmt":"2019-02-13T16:40:27","slug":"leetcode-133-clone-graph","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-133-clone-graph\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 133. Clone Graph"},"content":{"rendered":"\n

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label<\/code> (int<\/code>) and a list (List[UndirectedGraphNode]<\/code>) of its neighbors<\/code>. 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):<\/strong><\/p>\n\n\n\n

Nodes are labeled uniquely.We use #<\/code> as a separator for each node, and ,<\/code> as a separator for node label and each neighbor of the node.<\/p>\n\n\n\n

As an example, consider the serialized graph {0,1,2#1,2#2,2}<\/code>.<\/p>\n\n\n\n

The graph has a total of three nodes, and therefore contains three parts as separated by #<\/code>.<\/p>\n\n\n\n

  1. First node is labeled as 0<\/code>. Connect node 0<\/code> to both nodes 1<\/code> and 2<\/code>.<\/li>
  2. Second node is labeled as 1<\/code>. Connect node 1<\/code> to node 2<\/code>.<\/li>
  3. Third node is labeled as 2<\/code>. Connect node 2<\/code> to node 2<\/code> (itself), thus forming a self-cycle.<\/li><\/ol>\n\n\n\n

    Visually, the graph looks like the following:<\/p>\n\n\n\n

           1\n      \/ \\\n     \/   \\\n    0 --- 2\n         \/ \\\n         \\_\/\n<\/pre>\n\n\n\n
    Note<\/strong>: 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.<\/p>\n\n\n\n
    Solution: Queue + Hashtable<\/strong><\/h2>\n\n\n\n
    Time complexity: O(V+E)
    Space complexity: O(V+E)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, 44ms, 16.8MB\nclass Solution {\npublic:\n  UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {\n    if (!node) return nullptr;\n    typedef UndirectedGraphNode Node;\n    unordered_set done;\n    unordered_map m;    \n    queue q;\n    q.push(node);\n    while (!q.empty()) {\n      Node* s = q.front(); q.pop();\n      if (done.count(s)) continue;\n      done.insert(s);\n      if (!m.count(s))\n        m[s] = new Node(s->label);\n      Node* t = m[s];\n      for (Node* ss : s->neighbors) {\n        if (!m.count(ss))\n          m[ss] = new Node(ss->label);\n        q.push(ss);        \n        t->neighbors.push_back(m[ss]);\n      }\n    }    \n    return m[node];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,82,213],"class_list":["post-4844","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-hashtable","tag-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4844","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4844"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4844\/revisions"}],"predecessor-version":[{"id":4847,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4844\/revisions\/4847"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}