Clone Graph

Medium

The problem

Each Node has a Val and a list Neighbors of other nodes, and the graph is undirected and connected. You get one node of the graph. Return a deep copy of the whole graph: all new Node objects with the same values and the same connections, and return the copy of the node you were given. If node is nil, return nil.

Example 1
Input: adjacency list (node i holds the value i): 1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]. node = the node with value 1
Output: A new node with value 1 whose copy of the graph has the same neighbours: 1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]
The four nodes form a square. Every copied node must be a new object, not one from the original graph.
Example 2
Input: node = a single node with value 1 and no neighbours
Output: A new single node with value 1 and no neighbours
Example 3
Input: node = nil
Output: nil

Limits

0 ≤ number of nodes ≤ 100
Node values are unique, from 1 up to the number of nodes
No repeated edges and no node is its own neighbour

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Cycles mean you will meet the same node again. How do you reuse the copy you already made?

The idea

Map original → clone. DFS: if node is in the map return its clone; else create it, store it, then clone all neighbours.

Target: O(V + E) time

Go function shape

func cloneGraph(node *Node) *Node

Reference solution

Tested with go test. Try it yourself first, then compare.

// Node is the graph node used by clone-graph style problems.
type Node struct {
	Val       int
	Neighbors []*Node
}

// CloneGraph: the map from old node to its copy is also the visited set.
func CloneGraph(node *Node) *Node {
	if node == nil {
		return nil
	}
	copies := map[*Node]*Node{}
	var clone func(n *Node) *Node
	clone = func(n *Node) *Node {
		if c, ok := copies[n]; ok {
			return c
		}
		c := &Node{Val: n.Val}
		copies[n] = c // register BEFORE recursing, or cycles recurse forever
		for _, nb := range n.Neighbors {
			c.Neighbors = append(c.Neighbors, clone(nb))
		}
		return c
	}
	return clone(node)
}

Read the lesson: Graphs: BFS / DFS / Topological Sort