Clone Graph

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

http://www.lintcode.com/en/problem/clone-graph/

Solution

graph相关的题目很容易想到DFS和BFS。这里先把DFS吃透，BFS再说吧。。。

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // write your code here
        if(node==NULL) return NULL;
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mymap;
        return clone(node, mymap);
    }
private:
    UndirectedGraphNode *clone(UndirectedGraphNode *node, 
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> &map) {
        if(map.find(node) != map.end()) return map[node];//忘记了
        UndirectedGraphNode *newnode = new UndirectedGraphNode(node->label);
        map[node] = newnode;//clone一个node，然后再递归clone它所有的neighbors
        for(int i=0; i < node->neighbors.size(); i++) {
            newnode->neighbors.push_back(clone(node->neighbors[i], map));
        }
        return map[node];
    }
};

用栈实现DFS，不用recursion。先copy node，再copy neighbors。刚开始两个一起clone，半天通不过，因为neighbors总有重复计算的情况。

class Solution {
public:
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // write your code here
        if(node==NULL) return NULL;
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mymap;
        stack<UndirectedGraphNode*> stk;
        vector<UndirectedGraphNode*> allnodes;
        stk.push(node);
        while(stk.empty() == false) {
            UndirectedGraphNode *tmp = stk.top();
            if(mymap.find(tmp) == mymap.end()) {
                UndirectedGraphNode *newnode = new UndirectedGraphNode(tmp->label);
                mymap[tmp] = newnode;
                allnodes.push_back(tmp);
            }
            bool allVisited = true;
            for(int i=0; i < tmp->neighbors.size(); i++) {
                if(mymap.find(tmp->neighbors[i]) == mymap.end()) {
                    stk.push(tmp->neighbors[i]);
                    allVisited = false;
                    break;//不break也可以，不过就不是DFS了
                }
                //mymap[tmp]->neighbors.push_back(mymap[tmp->neighbors[i]]);
            }
            if(allVisited == true) {//一定要等所有的都访问过了才pop
                stk.pop();
            }
        }

        //clone neighbors
        for(int i=0; i<allnodes.size(); i++) {
            UndirectedGraphNode *tmpNode = allnodes[i];
            for(int j=0; j<tmpNode->neighbors.size(); j++) {
                mymap[tmpNode]->neighbors.push_back(mymap[tmpNode->neighbors[j]]);
            }
        }
        return mymap[node];
    }
};

轻度强迫症患者表示最好还是把BFS也搞了吧。。。

// Time:  O(|V| + |E|)
// Space: O(|V|)
class Solution {
public:
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // write your code here
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> map;
        queue<UndirectedGraphNode*> que;
        if(node == NULL) return NULL;
        que.push(node);
        map[node] = new UndirectedGraphNode(node->label);
        while(que.empty() == false) {
            UndirectedGraphNode *curNode = que.front();
            que.pop();
            for(int i=0; i<curNode->neighbors.size(); i++) {
                UndirectedGraphNode *curNei = curNode->neighbors[i];
                if(map.find(curNei) != map.end()) {
                    map[curNode]->neighbors.push_back(map[curNei]);
                } else {
                    UndirectedGraphNode *newnode = new UndirectedGraphNode(curNei->label);
                    map[curNei] = newnode;
                    map[curNode]->neighbors.push_back(newnode);//forgot at first
                    que.push(curNei);
                }
            }
        }
        return map[node];
    }
};