| 10 | } |
| 11 | |
| 12 | func cloneGraph(node *Node) *Node { |
| 13 | if node == nil { return node } // deal with nil case |
| 14 | m := make(map[int]*Node) |
| 15 | visited := make(map[int]bool) |
| 16 | // init queue |
| 17 | q := make([]*Node,1) |
| 18 | q[0] = node |
| 19 | // bfs |
| 20 | for len(q) != 0 { |
| 21 | curNode := q[0] |
| 22 | q = q[1:] |
| 23 | // append to m if curNode not visited yet |
| 24 | if m[curNode.Val] == nil { |
| 25 | m[curNode.Val] = new(Node) |
| 26 | m[curNode.Val].Val = curNode.Val |
| 27 | } |
| 28 | for _, j := range curNode.Neighbors { |
| 29 | if m[j.Val] == nil { |
| 30 | // not visited yet, append to q |
| 31 | q = append(q,j) |
| 32 | } |
| 33 | } |
| 34 | } |
| 35 | q = append(q,node) |
| 36 | visited[node.Val] = true |
| 37 | for len(q) != 0 { |
| 38 | // bfs |
| 39 | oldNode := q[0] |
| 40 | q = q[1:] |
| 41 | newNode := m[oldNode.Val] |
| 42 | for _, j := range oldNode.Neighbors { |
| 43 | nbidx := j.Val |
| 44 | newNode.Neighbors = append(newNode.Neighbors, m[nbidx]) |
| 45 | |
| 46 | // push q |
| 47 | if visited[j.Val] == false { |
| 48 | q = append(q,j) |
| 49 | visited[j.Val] = true |
| 50 | } |
| 51 | } |
| 52 | } |
| 53 | return m[node.Val] |
| 54 | } |
| 55 | |
| 56 | func main() { |
| 57 | node1 := new(Node) |