LeetCode/133.Clone Graph at master · xxkafu/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// solution:
// easy
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(node==NULL)
            return node;

        UndirectedGraphNode* newNode= new UndirectedGraphNode(node->label);
        queue<UndirectedGraphNode*> oribot;
        queue<UndirectedGraphNode*> newbot;
        unordered_map<int,UndirectedGraphNode*> hash;
        hash[newNode->label]=newNode;
        oribot.push(node);
        newbot.push(newNode);
        while(!oribot.empty()){
            UndirectedGraphNode* oriSource=oribot.front();
            UndirectedGraphNode* newSource=newbot.front();
            vector<UndirectedGraphNode *> oriNeis=oriSource->neighbors;
            for(int i=0; i<oriNeis.size();i++){
                UndirectedGraphNode* oriNei=oriNeis[i];
                if(hash.find(oriNei->label)==hash.end()){
                    UndirectedGraphNode* newNei= new UndirectedGraphNode(oriNei->label);
                    oribot.push(oriNei);
                    newbot.push(newNei);
                    hash[newNei->label]=newNei;
                }
                (newSource->neighbors).push_back(hash[oriNei->label]);
            }
            oribot.pop();
            newbot.pop();
        }
        return newNode;

    }
};