Clone Graph

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

OJ's undirected graph serialization: Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Solution: DFS

We can use a hash table to keep track of copied nodes. If the node is connecting to itself, we just push itself to its neighbors list as there's no need to create a new one.

    UndirectedGraphNode *cloneGraphUtil(UndirectedGraphNode *node, unordered_map<int, UndirectedGraphNode*> &m) {
        if (m.count(node->label)) return m[node->label];

        UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
        for (auto neighbor: node->neighbors) {
            if (node == neighbor) {
                newNode->neighbors.push_back(newNode);            
            } else {
                newNode->neighbors.push_back(cloneGraphUtil(neighbor, m));
            }
        }

        m[node->label] = newNode;
        return newNode;
    }

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
        unordered_map<int, UndirectedGraphNode*> m;
        return cloneGraphUtil(node, m);
    }

Solution: BFS

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;

        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m;
        queue<UndirectedGraphNode*> q;
        q.push(node);

        UndirectedGraphNode* copy = new UndirectedGraphNode(node -> label);
        m[node] = copy;
        while (!q.empty()) {
            UndirectedGraphNode* cur = q.front();
            q.pop();

            for (auto neigh : cur->neighbors) {
                if (!m.count(neigh)) {
                    UndirectedGraphNode* neigh_copy = new UndirectedGraphNode(neigh -> label);
                    m[neigh] = neigh_copy;
                    q.push(neigh);
                }
                m[cur]->neighbors.push_back(m[neigh]);
            }
        }
        return copy; 
    }

Solution: DFS

    UndirectedGraphNode *cloneGraphUtil(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> &m) {
        if (!node) return NULL;

        if (!m.count(node)) {
            m[node] = new UndirectedGraphNode(node->label);
            for (auto  neigh: node->neighbors) {
                m[node] -> neighbors.push_back(cloneGraphUtil(neigh, m));
            }
        }
        return m[node];
    }

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m;
        return cloneGraphUtil(node, m);
    }