---
tags: leetcode
---

# [133. Clone Graph](https://leetcode.com/problems/clone-graph/)
---
# My Solution
## Solution 1: DFS
### The Key Idea for Solving This Coding Question
### C++ Code 1

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    Node *cloneGraph(Node *node) {
        unordered_map<Node *, Node *> visited;

        return dfs(node, visited);
    }

private:
    Node *dfs(Node *org, unordered_map<Node *, Node *> &visited) {
        if (org == nullptr) {
            return nullptr;
        }

        Node *clone = new Node(org->val);
        visited[org] = clone;
        for (int i = 0; i < org->neighbors.size(); ++i) {
            Node *orgNext = org->neighbors[i];
            auto nextIter = visited.find(orgNext);
            if (nextIter != visited.end()) {
                // We have visited next.
                Node *cloneNext = nextIter->second;
                clone->neighbors.push_back(cloneNext);
            } else {
                // We haven't visited next.
                clone->neighbors.push_back(dfs(orgNext, visited));
            }
        }

        return clone;
    }
};

### C++ Code 2

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    Node *cloneGraph(Node *node) {
        if (node == nullptr) {
            return nullptr;
        }
        
        Node *cloned = new Node(node->val);
        originalToCloned[node] = cloned;
        for (Node *next : node->neighbors) {
            auto iter = originalToCloned.find(next);
            if (iter != originalToCloned.end()) {
                // We have visited and cloned next.
                // iter->second is the cloned node of next.
                cloned->neighbors.push_back(iter->second);
            } else {
                cloned->neighbors.push_back(cloneGraph(next));
            }
        }
        
        return cloned;
    }
    
private:
    unordered_map<Node *, Node *> originalToCloned;
};

### Time Complexity
$O(V+E)$
$V$ is the total number of nodes in the graph.
$E$ is the total number of edges in the graph.
### Space Complexity
$O(V+E)$
## Solution 2: BFS
### The Key Idea for Solving This Coding Question
### C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    Node *cloneGraph(Node *node) {
        if (node == nullptr) {
            return nullptr;
        }

        unordered_map<Node *, Node *> visited;
        Node *clone = new Node(node->val);
        queue<Node *> q;

        q.push(node);
        visited[node] = clone;
        while (!q.empty()) {
            Node *orgCurr = q.front();
            q.pop();

            Node *cloneCurr = visited[orgCurr];
            for (Node *orgNext : orgCurr->neighbors) {
                auto nextIter = visited.find(orgNext);
                if (nextIter != visited.end()) {
                    // We have visited orgNext.
                    Node *cloneNext = nextIter->second;
                    cloneCurr->neighbors.push_back(cloneNext);
                } else {
                    // We haven't visited orgNext.
                    Node *cloneNext = new Node(orgNext->val);
                    cloneCurr->neighbors.push_back(cloneNext);
                    q.push(orgNext);
                    visited[orgNext] = cloneNext;
                }
            }
        }

        return clone;
    }
};

### Time Complexity
$O(V+E)$
$V$ is the total number of nodes in the graph.
$E$ is the total number of edges in the graph.
### Space Complexity
$O(V+E)$
# Reference
[No. 133 - Clone Graph](https://hackmd.io/@Ji0m0/B1dUOaRjN/https%3A%2F%2Fhackmd.io%2F%40Ji0m0%2Frk3SWptau)
# Miscellane
<!--
# Test Cases

[[2,4],[1,3],[2,4],[1,3]]

[[]]

[]

[[2],[1]]

-->