Clone Graph

package main

import "fmt"

type Node struct {
	Val       int
	Neighbors []*Node
}

func cloneGraph(node *Node) *Node {
	if node == nil {
		return nil
	}
	cloned := map[int]*Node{}

	var dfs func(*Node) *Node
	dfs = func(n *Node) *Node {
		if c, ok := cloned[n.Val]; ok {
			return c
		}
		copy := &Node{Val: n.Val}
		cloned[n.Val] = copy
		for _, nb := range n.Neighbors {
			copy.Neighbors = append(copy.Neighbors, dfs(nb))
		}
		return copy
	}
	return dfs(node)
}

func main() {
	// Build: 1 -- 2 -- 3 -- 1
	n1 := &Node{Val: 1}
	n2 := &Node{Val: 2}
	n3 := &Node{Val: 3}
	n1.Neighbors = []*Node{n2, n3}
	n2.Neighbors = []*Node{n1, n3}
	n3.Neighbors = []*Node{n1, n2}

	clone := cloneGraph(n1)
	fmt.Println(clone.Val, len(clone.Neighbors))             // 1 2
	fmt.Println(clone.Neighbors[0].Val)                       // 2
	fmt.Println(clone != n1, clone.Neighbors[0] != n2)        // true true
}