# c++ DFS solution with O(1) space

• ``````/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
*     int label;
*     vector<UndirectedGraphNode *> neighbors;
*     UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *copy(UndirectedGraphNode *node)
{
int i;
if(!node) return node;
vector<UndirectedGraphNode *>& neighbors=node->neighbors;
if(neighbors.size() && ((neighbors[neighbors.size()-1]!=node) && (neighbors[neighbors.size()-1]->label==node->label))) return neighbors[neighbors.size()-1];
UndirectedGraphNode* copy_node=new UndirectedGraphNode(node->label);
neighbors.push_back(copy_node);
for(i=0;i<neighbors.size()-1;i++)
copy(neighbors[i]);
return copy_node;
}
{
int i;
if(!node) return;
vector<UndirectedGraphNode *>& neighbors=node->neighbors;
UndirectedGraphNode *cur=neighbors[neighbors.size()-1];
if((cur->neighbors).size()) return;
for(i=0;i<neighbors.size()-1;i++)
{
UndirectedGraphNode *to=neighbors[i];
(cur->neighbors).push_back((to->neighbors)[(to->neighbors).size()-1]);
}
for(i=0;i<neighbors.size()-1;i++)
{
UndirectedGraphNode *to=neighbors[i];
}
return;
}
void del(UndirectedGraphNode *node)
{
int i;
if(!node) return;
vector<UndirectedGraphNode *>& neighbors=node->neighbors;
if(!neighbors.size() || (neighbors[neighbors.size()-1]==node) || (neighbors[neighbors.size()-1]->label!=node->label)) return;

neighbors.pop_back();
for(i=0;i<neighbors.size();i++)
del(neighbors[i]);
return;
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return NULL;
UndirectedGraphNode *new_node=copy(node);
del(node);
return new_node;
}
};
``````

1. The idea behind your code without using hash_map is very smart.
2. The space complexity is O(n), not O(1) because of recursion.
I rewrite your code to become more readable. OK? And I give an example to help other people understand your code.
Thanks for sharing.:)
``````class Solution {
public:
UndirectedGraphNode *copy(UndirectedGraphNode *node) {
vector<UndirectedGraphNode*> &neighbors = node->neighbors;
if(!neighbors.empty() && neighbors.back() != node && neighbors.back()->label == node->label)
return neighbors.back();

UndirectedGraphNode *copy_node = new UndirectedGraphNode(node->label);
neighbors.push_back(copy_node);
for (int i = 0; i < neighbors.size() - 1; ++i)
copy(neighbors[i]);
return copy_node;
}
vector<UndirectedGraphNode*> &neighbors = node->neighbors;
UndirectedGraphNode *last = neighbors.back();
if (!last->neighbors.empty()) return;
for (int i = 0; i < neighbors.size() - 1; ++i) {
UndirectedGraphNode *to = neighbors[i];
last->neighbors.push_back(to->neighbors.back());
}
for (int i = 0; i < neighbors.size() - 1; ++i)
}
void reset(UndirectedGraphNode *node) {
vector<UndirectedGraphNode*> &neighbors = node->neighbors;
if(neighbors.empty() || neighbors.back() == node || neighbors.back()->label != node->label)
return;

neighbors.pop_back();
for (auto v : neighbors) reset(v);
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return nullptr;
UndirectedGraphNode *new_node(copy(node));
reset(node);
return new_node;
}
};
``````

Example:

```       1                0 | 1 2
/ \               1 | 0 2
/   \              2 | 2 2
0 --- 2
/ \
\_/

Step1: copy
0 | 1 2 0
1 | 2 0 1
2 | 2 2 2

0 | 1 2 0     0 |
1 | 2 0 1     1 |
2 | 2 2 2     2 |

0 | 1 2 0     0 | 1 2
1 | 2 0 1     1 |
2 | 2 2 2     2 |

0 | 1 2 0     0 | 1 2
1 | 2 0 1     1 | 2 0
2 | 2 2 2     2 |

0 | 1 2 0     0 | 1 2
1 | 2 0 1     1 | 2 0
2 | 2 2 2     2 | 2 2

Step 3: recovery the original graph
0 | 1 2 0
1 | 2 0 1
2 | 2 2 2

0 | 1 2
1 | 2 0 1
2 | 2 2 2

0 | 1 2
1 | 2 0
2 | 2 2 2

0 | 1 2
1 | 2 0
2 | 2 2
```

• @xpfxzxc yes, your are right.the space is O(n).besides,thanks for your optimization and examples

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.