leetcode/code/133.clone-graph.cpp at main · SocioDroid/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
// 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:

    map<int, Node*> nodes;
    Node* cloneGraph(Node* node) {
        if(!node)
            return NULL;
        set<Node*> visited;
        return dfs(node, visited);
    }


    Node* dfs(Node* node, set<Node*>& visited){
        if(visited.find(node) != visited.end())
            return nodes[node->val];
        visited.insert(node);
        Node* ans = new Node(node->val);
        nodes[ans->val] = ans;
        // cout<<"For : "<<node->val<<endl;
        for(auto i : node->neighbors){
            ans->neighbors.push_back(dfs(i, visited));
        }

        // cout<<"For : "<<ans->val<<"\t";
        // for(auto i : ans->neighbors){
        //     cout<<i->val<<"->";
        // }
        // cout<<endl;
        return ans;
    }
};