c++ DFS solution with O(1) space


  • 1
    S
    /**
     * 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;
        }
        void link(UndirectedGraphNode *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];
                link(to);
            }
            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);
            link(node);
            del(node);
            return new_node;
        }
    };
    

  • 0
    X

    @shadowxh Hi, shadowxh.

    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;
        }
        void link(UndirectedGraphNode *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)
                link(neighbors[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));
            link(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
    
    Step 2: link
    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
    

  • 0
    S

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


Log in to reply
 

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