133 - Clone Graph

Clone Graph

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 #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. 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
Hide Similar Problems
(H) Copy List with Random Pointer

考的应该就是 deep copy 了。
先写了一个两个hash表的solution，一个表放 label 跟旧节点指针的关系，另一个放新旧节点的关系。
先 dfs 得到所有的点，存在第一张 hash 表，跟着创建新节点，建立第二张 hash 表，
然后再 dfs2 （清空第一张表），依样画葫芦建立新节点之间的连接关系即可。

查了一下，不少帖子都提到一个solution，用一张 hash 表解决问题，具体的做法是，一遍 dfs，一边创建新节点。
之前想过一张表搞定，但建立联系的时候，没想明白其他节点还没创建咋办？总不能先空着吧。
高人的做法是，就在建立联系的地方，递归调用 dfs，创建需要的新节点，返回其指针并把指针放进新表里，NND，哥不够狠啊。

/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
*     int label;
*     vector<UndirectedGraphNode *> neighbors;
*     UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
    //-------------------------------- slution with 2 hash tables, 2 dfs --------------------------------
    UndirectedGraphNode *cloneGraph_2maps(UndirectedGraphNode *node) {
        if(NULL == node)
            return node;

        unordered_map<int, UndirectedGraphNode*> buf;
        dfs(node, buf);

        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> buf2;
        for(auto b : buf)
        {
            UndirectedGraphNode* tmp = new UndirectedGraphNode(b.first);
            buf2[b.second] = tmp;
        }

        buf.clear();
        UndirectedGraphNode* rst = buf2[node];
        dfs2(node, buf, rst, buf2);

        return rst;
    }
   
    void dfs(UndirectedGraphNode* node, unordered_map<int, UndirectedGraphNode*>& buf)
    {
        if(buf.end() == buf.find(node->label))
        {
            buf[node->label] = node;
           
            for(auto nb : node->neighbors)
                dfs(nb, buf);
        }
    }

    void dfs2(UndirectedGraphNode* node, unordered_map<int, UndirectedGraphNode*>& buf,
            UndirectedGraphNode*& rst, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>& buf2)
    {
        if(buf.end() == buf.find(node->label))
        {
            for(auto nb : node->neighbors)
            {
                UndirectedGraphNode* newNighbor = buf2[nb];
                (rst->neighbors).push_back(newNighbor);

                buf[node->label] = node;
                dfs2(nb, buf, newNighbor, buf2);
            }
        }
    }

    //------------------------------- slution with 1 hash table, 1 dfs -------------------------------
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(NULL == node)
            return node;

        unordered_map<int, UndirectedGraphNode*> buf;
        return dfs3(node, buf);
    }

    // building new nodes while dfs
    UndirectedGraphNode* dfs3(UndirectedGraphNode* node, unordered_map<int, UndirectedGraphNode*>& buf)
    {
        if(buf.end() == buf.find(node->label))
        {
            UndirectedGraphNode* newnode = new UndirectedGraphNode(node->label);
            buf[node->label] = newnode;
           
            for(auto nb : node->neighbors)
                (newnode->neighbors).push_back(dfs3(nb, buf));
           
            return newnode;
        }
        return buf[node->label];
    }
};
84 ms, 76 ms.