达式等价)
思路：题目的要求是让我们实现一个图的深拷贝。深拷贝指的是复制另外一个对象到自己的对象中，且两者不共享一个内存区，浅拷贝指的是两者共享一个内存区。所以我们需要new 来开辟新的内存区执行拷贝。还要注意一个问题。我们这个图实际上是个有向图，如果A有一个相邻顶点B，则A->B, 但是B能否到A取决于B是否有相邻顶点A. 也就是说如果B能达到A，说明图中存在环，如果不考虑环的存在，我们在拷贝中可能形成死循环。
假设我们从图的A点出发，进行拷贝得到A(A2), 发现A有一个相邻顶点B，然后进行拷贝得到B(B2),然后链接A2->B2，使得B2成为A2的相邻顶点。接着，我们操作B, 发现B有一个相邻顶点A, 而A我们是已经进行过拷贝的了。如果我们又对A再次进行拷贝, 将形成个死循环，我们要做的仅是将B2->A2连接起来。如何才能避免这种再次拷贝呢？我们只需要一个map即可，每次我们做一份拷贝，就放入map中，下次查询，如果是已经有的copy就不再继续拷贝，只是连接。如果没有，就做拷贝，然后连接，然后放入map. map的key是原来的顶点，value是原来定点的copy版。<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+vt/M5b3iys2/ydLUv7TPwtXixqrOxNXCo7pjbG9uZSBncmFwaCBwYXJ0PC9wPgo8cD5xdWV1ZdbQzqy7pLXEysfOtLSmwO1uZWlnaGJvcrXEtqW146Os0rLKx860v72xtLn9tcS94bXjoaM8L3A+CjxwPm1hcNbQtcRrZXksdmFsdWW31rHwsaO05mNvcHm5/bXE1K292rXjus1jb3B5vdq146GjPC9wPgo8cD7O0sPHz8hjb3B5uPm94bXjo6zIu7rzt8XI67bTwdCjrL3Tz8LAtL340NC547bI08XPyMvRy/ew7Leoo6yyu7bPtKbA7bbTwdDW0LXEvdq146Osz8i1w7W9tbHHsL3ateO6zcbkY29webDmsb6jrMi7uvPF0LbPtbHHsL3ateO1xMv509BuZWlnaGJvcnMsIMjnufvS0b6tv72xtLn9o6zWu9f2way907LZ1/ejrMjnufvDu9PQv72xtLn9o6zPyL340NC/vbG0o6zIu7rzway906OsyLu687fFyOttYXC6zXF1ZXVlLrWxttPB0NbQtcTUqsvYtry0psDtzeqjrEJGU73hyvijrLe1u9hjb3B5uPm94bXjoaM8L3A+CjxwPjxzdHJvbmc+QXR0ZW50aW9uOjwvc3Ryb25nPjwvcD4KPHA+PHN0cm9uZz7W99Kqyse7+bG+t723qLXEstnX98rHt/HKudPD1f3It6OsvNPJz9K70KnPuL3atcSy2df3o6zQ6NKq19DPuMDtveK6zbzH0uSho8r009q7+bG+stnX97XE1+m6z6OsyN3S17vsz/2jrNOmuMPX0M+40dC+v8/CtPrC66GjPC9zdHJvbmc+PC9wPgo8cD48c3Ryb25nPjEuINei0uK7+bG+stnX97XEyrnTw6OsscjI573hubnM5da41eu1xMTasr/UqsvYtcS199PDysfTw8TEuPay2df3t/ujvw=="->"还是"." 还有分清楚操作的对象，然后决定用C++内的什么方法进行调用和操作。
curClone->neighbors.push_back(neighborClone); // 给curClone添加复制的neighbor
2. 注意我们在拷贝过程中，总是要对原节点进行拷贝，处理连接关系时，也要在拷贝版本间进行连接。
curClone->neighbors.push_back(neighborClone); // 给curClone添加复制的neighbor
3. map添加pair对，需要加“{}”。
cmap.insert({neighbor, neighborClone}); //添加到map中
复杂度：O(N),因为我们把每个结点都访问一遍，空间复杂度是栈或者队列加上map的大小，不会超过O(N)。
AC Code: (BFS)
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector
neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node == NULL) return NULL;
//开辟新的空间存储copy
UndirectedGraphNode* copy = new UndirectedGraphNode(node->label);
//查找去重用的map unordered_map
放原始node和其复制品 unordered_map
cmap; //存储的队列，进行BFS queue
graphQ; graphQ.push(node); //根结点添加到队列 cmap.insert({node, copy}); //把根节点和其复制品放入map while(!graphQ.empty()) { UndirectedGraphNode* cur = graphQ.front(); //当前处理对象 graphQ.pop(); UndirectedGraphNode* curClone = cmap[cur]; //当前处理对象的复制品 因为在前面的neighbor里已经被创建 //对当前顶点的每一个neighbor进行判断，因为有的neighbor已经被复制，有的没有 for(int i = 0; i < cur->neighbors.size(); i++) { UndirectedGraphNode* neighbor = cur->neighbors[i]; //如果之前没有拷贝过 if(cmap.find(neighbor) == cmap.end()) { UndirectedGraphNode* neighborClone = new UndirectedGraphNode(neighbor->label); curClone->neighbors.push_back(neighborClone); //给curClone添加复制的neighbor cmap.insert({neighbor, neighborClone}); //添加到map中 graphQ.push(neighbor); //添加到队列为了将来的遍历 } else // 之前已经被复制过的neighbor { UndirectedGraphNode* neighborClone = cmap[neighbor]; //从map中取出之前的copy版本 curClone->neighbors.push_back(neighborClone); // 给curClone添加复制的neighbor } } } return copy; } };
AC Code: (DFS) 将存储改成用stack存储结点，得到深度优先搜索。
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector
neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node == NULL) return NULL;
stack
stk; unordered_map
cmap; UndirectedGraphNode* copy = new UndirectedGraphNode(node->label); stk.push(node); cmap.insert({node, copy}); while(!stk.empty()) { UndirectedGraphNode* cur = stk.top(); stk.pop(); UndirectedGraphNode* curClone = cmap[cur]; //浅拷贝，开始顶点的curClone和copy指向同一个地址 for(int i = 0; i < cur->neighbors.size(); i++) { UndirectedGraphNode* neighbors = cur->neighbors[i]; if(cmap.find(neighbors) == cmap.end()) { UndirectedGraphNode* neighborsClone = new UndirectedGraphNode(neighbors->label); curClone->neighbors.push_back(neighborsClone); cmap.insert({neighbors, neighborsClone}); stk.push(neighbors); } else { UndirectedGraphNode* neighborsClone = cmap[neighbors]; curClone->neighbors.push_back(neighbo