[LeetCode] Clone Graph

Problem Statement (link):

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 #.

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

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Analysis:
It's a standard graph traversal problem. Herein we use DFS to solve this problem.

We keep an unordered_map<int, Node*> visited to maintain the visited nodes - the label and the pointer to it. Note that the pointer is the pointer to nodes in the new graph.

A big difference between graph and tree is that cycles may exist. So whenever we visit a node, we add the node into the visited map. For each of its neighbors, we then check the visited map if the neighbor's label exists. Here we assume the label is unique for each node.

- If the label exists, it means we have visited this neighbor somewhere else - even if it is not currently in the neighbor's vector, we need to add the neighbor's pointer to the vector - by looking up in the visited map (Again, remember the visited map stores the label and new node's pointer).

- If the label doesn't exist, it implies that we haven't traversed the node, we then need to do a DFS recursion on that node.

Additionally, if the label/value of each node is different, we only need to change the visited map to unordered_map<Node*, Node> visited, where the two pointers are the pointer to node in the old graph and that to the corresponding node in the new graph.

Code:

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

class Solution {
    typedef UndirectedGraphNode Node;

public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node==NULL) return NULL;
        unordered_map<int, Node*> visited;
        return recur(node, visited);
    }

    Node *recur(Node *node, unordered_map<int, Node*>& visited) {
        Node *newNode=new Node(node->label);
        visited.emplace(node->label, newNode);

        for (int i=0; i<node->neighbors.size(); i++) {
            if (visited.find(node->neighbors[i]->label)==visited.end())
                newNode->neighbors.push_back(recur(node->neighbors[i], visited));
            else
                newNode->neighbors.push_back(visited[node->neighbors[i]->label]);
        }
        return newNode;
    }
};