133. Clone Graph
C++，dfs，深拷贝。。。
其实就是深拷贝的一个实现，深拷贝就是对于所有的指针成员，不能仅仅是赋值，还要重新分配空间。
- 深拷贝反应在本题中就是，所有的结点需要重新
new出来，而不是直接赋值。 - 整体的思路依然是dfs，跑遍原图中每个结点，然后根据原结点生成新结点。
- 要注意的地方就是，因为图存在环，所以要标记访问过的结点，避免重复形成死循环：
- 如果该结点已经被访问过，则不再遍历该结点，而是直接将指针值赋给自己邻接点数组—-浅拷贝；
- 如果该结点没有被访问过，则继续dfs遍历该结点，并将产生的新结点—-深拷贝；
拷贝过程见代码：
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* visited[101] = {nullptr};
Node* cloneGraph(Node* node) {
int size = node->neighbors.size();
Node *root = new Node(node->val, vector<Node*> {});
visited[node->val] = root;
for (int i = 0; i < size; i++) {
if (!visited[node->neighbors[i]->val])
root->neighbors.push_back(cloneGraph(node->neighbors[i]));
else
root->neighbors.push_back(visited[node->neighbors[i]->val]);
}
return root;
}
};
