11-liner in Python/C++

  • 6

    First create nodes, than create connections. Easy-peasy.

    class Solution(object):
        def cloneGraph(self, start):
            if not start: return None
            new, old, queue = {}, {}, [start]
            for node in queue:
                if node.label in new: continue
                new[node.label] = UndirectedGraphNode(node.label)
                old[node.label] = node
                for neigh in node.neighbors: queue += neigh,
            for label in new:
                for neighl in old[label].neighbors:
                    new[label].neighbors += new[neighl.label],
            return new.pop(start.label, None)

    C++ version, same amount of lines (more or less):

    typedef UndirectedGraphNode UGNode;
    class Solution {
        UGNode* cloneGraph(UGNode* start) {
            if (start == NULL) return NULL;
            map<int, UGNode*> news, olds;
            queue<UGNode*> q; q.push(start);
            while (!q.empty()) {
                auto node = q.front(); q.pop();
                if (news.count(node->label)) continue;
                news[node->label] = new UGNode(node->label);
                olds[node->label] = node;
                for (auto neigh: node->neighbors) q.push(neigh);
            for (auto keyval: news) {
                for (auto neighl: olds[keyval.first]->neighbors)
            return news[start->label];

Log in to reply

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