Clone Graph

• Lintcode : 137 / Leetcode : 133
• Level : Medium

Problem

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

You need to return a deep copied graph, which has the same structure as the original graph, and any changes to the new graph will not have any effect on the original graph.

Example
Example1

Input:
{1,2,4#2,1,4#4,1,2}
Output: 
{1,2,4#2,1,4#4,1,2}
Explanation:
1------2  
 \     |  
  \    |  
   \   |  
    \  |  
      4   
Clarification
How we serialize an undirected graph: http://www.lintcode.com/help/graph/

Notice
You need return the node with the same label as the input node.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(edges)
space: O(n)

Answer

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
    UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) {
        // corner case 
        if (node == nullptr) return nullptr;

        set<UndirectedGraphNode*> repeat;
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mirror;
        queue<UndirectedGraphNode*> q;
        q.push(node);
        repeat.insert(node);
        mirror[node] = new UndirectedGraphNode(node -> label);
        while(!q.empty()) {
            UndirectedGraphNode* x = q.front(); q.pop();
            for (int i = 0; i < x -> neighbors.size(); i++) {
                if (mirror.find(x -> neighbors[i]) == mirror.end()) {
                    UndirectedGraphNode* newNode = new UndirectedGraphNode(x -> neighbors[i] -> label);
                    mirror[x -> neighbors[i]] = newNode;
                }
                mirror[x] -> neighbors.push_back(mirror[x -> neighbors[i]]);
                if (repeat.find(x -> neighbors[i]) == repeat.end()) q.push(x -> neighbors[i]);
                repeat.insert(x -> neighbors[i]);
            }
        }
        return mirror[node];
    }
};

tags: BFS

​