Clone Graph Solutions in C++

// Source : https://oj.leetcode.com/problems/clone-graph/
// Author : Hao Chen
// Date   : 2014-10-12



/**
 * 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 NULL;
        
        //create a map, key is source node, value is clone node.
        map<UndirectedGraphNode*, UndirectedGraphNode*> cloneMap;
        
        //using queue for breadth first search
        queue<UndirectedGraphNode*> q;
        q.push(node);
        
        //clone the root
        UndirectedGraphNode* cloneNode = new UndirectedGraphNode(node->label);
        cloneMap[node] = cloneNode;
        
        //breadth first search
        while(!q.empty()){
            UndirectedGraphNode* n = q.front();
            q.pop();
            //for each neighbors
            for(int i=0; i<n->neighbors.size(); i++){
                UndirectedGraphNode* neighbor= n->neighbors[i];
                //not existed in cloneMap
                if (cloneMap.find(neighbor)==cloneMap.end()){
                    //clone a node
                    UndirectedGraphNode* newNode = new UndirectedGraphNode(neighbor->label);
                    cloneMap[n]->neighbors.push_back(newNode);
                    cloneMap[neighbor] = newNode;
                    
                    //put the neighbors into the queue
                    q.push(neighbor);
                }else{
                    cloneMap[n]->neighbors.push_back(cloneMap[neighbor]);
                }
            }
        }
        
        return cloneNode;
    }
};

#include <vector>
using std::vector;
#include <unordered_map>
using std::unordered_map;

struct UndirectedGraphNode {
    int label;
    vector<UndirectedGraphNode *> neighbors;
    UndirectedGraphNode(int x) : label(x) {};
};

class Solution {
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> map;
    void dfs(UndirectedGraphNode *node) {
        if (map.find(node) != map.end()) return;
        map[node] = new UndirectedGraphNode(node->label);
        for (UndirectedGraphNode *neighbor : node->neighbors) {
            dfs(neighbor);
            map[node]->neighbors.push_back(map[neighbor]);
        }
    }
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return node;
        dfs(node);
        return map[node];
    }
};

/// Source : https://leetcode.com/problems/clone-graph/description/
/// Author : liuyubobobo
/// Time   : 2018-08-30

#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>

using namespace std;

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

/// Using Two Stacks and HashMap from label to Node
/// Time Complexity: O(V+E)
/// Space Complexity: O(V)
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

        if(node == NULL)
            return NULL;

        UndirectedGraphNode* ret = new UndirectedGraphNode(node->label);

        stack<UndirectedGraphNode*> stack1;
        stack1.push(node);
        unordered_map<int, UndirectedGraphNode*> visited;
        visited[ret->label] = ret;

        stack<UndirectedGraphNode*> stack2;
        stack2.push(ret);

        while(!stack1.empty()){
            UndirectedGraphNode* old_cur = stack1.top();
            stack1.pop();

            UndirectedGraphNode* new_cur = stack2.top();
            stack2.pop();

            for(UndirectedGraphNode *next: old_cur->neighbors) {
                if (visited.find(next->label) == visited.end()) {
                    visited[next->label] = new UndirectedGraphNode(next->label);
                    stack1.push(next);
                    stack2.push(visited[next->label]);
                }
                new_cur->neighbors.push_back(visited[next->label]);
            }
        }
        return ret;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/clone-graph/description/
/// Author : liuyubobobo
/// Time   : 2018-09-14

#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>

using namespace std;

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

/// Using Only One Stacks and HashMap from Node to Node
/// Time Complexity: O(V+E)
/// Space Complexity: O(V)
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

        if(node == NULL)
            return NULL;

        UndirectedGraphNode* ret = new UndirectedGraphNode(node->label);
        stack<UndirectedGraphNode*> stack;
        stack.push(node);
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> nodeMap;
        nodeMap[node] = ret;
        while(!stack.empty()){
            UndirectedGraphNode* cur = stack.top();
            stack.pop();
            for(UndirectedGraphNode *next: cur->neighbors) {
                if (!nodeMap.count(next)) {
                    nodeMap[next] = new UndirectedGraphNode(next->label);
                    stack.push(next);
                }
                nodeMap[cur]->neighbors.push_back(nodeMap[next]);
            }
        }
        return ret;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/clone-graph/description/
/// Author : liuyubobobo
/// Time   : 2018-09-14

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

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

/// DFS
/// Time Complexity: O(V+E)
/// Space Complexity: O(V)
class Solution {

public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

        if(node == NULL)
            return NULL;

        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> nodeMap;
        return dfs(node, nodeMap);
    }

private:
    UndirectedGraphNode *dfs(UndirectedGraphNode *node,
                             unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>& nodeMap){

        if(nodeMap.count(node))
            return nodeMap[node];

        nodeMap[node] = new UndirectedGraphNode(node->label);
        for(UndirectedGraphNode* next: node->neighbors)
            nodeMap[node]->neighbors.push_back(dfs(next, nodeMap));
        return nodeMap[node];
    }
};


int main() {

    return 0;
}