Clone Graph

LeetCode #133

Description:

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

Example:

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Idea:

BFS, 用queue。

用unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> copied来记录node是否created，这个也能用来快速找到对应的新node。

explore children的时候，判断是否已经copied，是的话，connect就行，不是的话，先create copy，然后connect。connect是单向。

Code:

public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(node == NULL) return NULL;

        UndirectedGraphNode * copy_root = new UndirectedGraphNode(node->label);
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> copied;
        copied[node]=copy_root;

        queue<UndirectedGraphNode *> frontier;
        frontier.push(node);

        while(!frontier.empty()){
            UndirectedGraphNode * curr_node = frontier.front();
            frontier.pop();

            for(auto e: curr_node->neighbors){
                if(copied.find(e)==copied.end()){
                    UndirectedGraphNode * copy_e = new UndirectedGraphNode(e->label);
                    copied[e]=copy_e;
                    copied[curr_node]->neighbors.push_back(copy_e);
                    frontier.push(e);
                }
                else{
                    copied[curr_node]->neighbors.push_back(copied[e]);
                }

            }

        }

        return copy_root;

    }