Share both of my C++ DFS and BFS solutions


  • 1
    F

    DFS seems always easier to code. It took me almost double time to pass the BFS version.

    ///DFS
    class Solution {
        unordered_map<int, UndirectedGraphNode *> m_map;
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if (node == nullptr)
                return nullptr;
            auto iter = m_map.find(node->label);
            if (iter != m_map.end())
                return iter->second;
            auto new_node = new UndirectedGraphNode(node->label);
            m_map[node->label] = new_node;
            for (auto neighbor : node->neighbors)
                new_node->neighbors.push_back(cloneGraph(neighbor));
            return new_node;
        }
    };
    ///BFS
    class Solution {
        unordered_map<int, UndirectedGraphNode *> m_map;
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if (node == nullptr)
                return nullptr;
            queue<UndirectedGraphNode *> the_q;
            auto root_node = new UndirectedGraphNode(node->label);
            m_map[root_node->label] = root_node;
            the_q.push(node);
            while (the_q.size())
            {
                auto cur = the_q.front(); the_q.pop();
                auto new_node = m_map[cur->label];
                for (auto neighbor : cur->neighbors)
                {
                    auto iter = m_map.find(neighbor->label);
                    UndirectedGraphNode * new_neighbor = nullptr;
                    if (iter == m_map.end())
                    {
                        new_neighbor = new UndirectedGraphNode(neighbor->label);
                        m_map[new_neighbor->label] = new_neighbor;
                        the_q.push(neighbor);
                    }else
                        new_neighbor = iter->second;
                    new_node->neighbors.push_back(new_neighbor);
                }
            }
            return root_node;
        }
    };

Log in to reply
 

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