(n int, edges [][]int)
| 1 | package graph_valid_tree_261 |
| 2 | |
| 3 | func validTree(n int, edges [][]int) bool { |
| 4 | if len(edges) < 1 { |
| 5 | return n == 1 |
| 6 | } |
| 7 | |
| 8 | // If the number of edges is not equal to the number of |
| 9 | // vertices - 1, then there is a cycle in the graph, and |
| 10 | // it is not a tree. We can use this for the question |
| 11 | // since a tree must be a connected graph. |
| 12 | if len(edges) != n-1 { |
| 13 | return false |
| 14 | } |
| 15 | |
| 16 | // create an adjacency list from the edges |
| 17 | adjList := make(map[int][]int) |
| 18 | for _, v := range edges { |
| 19 | adjList[v[0]] = append(adjList[v[0]], v[1]) |
| 20 | adjList[v[1]] = append(adjList[v[1]], v[0]) |
| 21 | } |
| 22 | |
| 23 | // ensure that the undirected graph is connected |
| 24 | start := edges[0][0] |
| 25 | seen := map[int]bool{start: true} |
| 26 | q := []int{start} |
| 27 | for len(q) != 0 { |
| 28 | dq := q[0] |
| 29 | q = q[1:] |
| 30 | for _, e := range adjList[dq] { |
| 31 | _, ok := seen[e] |
| 32 | if !ok { |
| 33 | seen[e] = true |
| 34 | q = append(q, e) |
| 35 | } |
| 36 | } |
| 37 | } |
| 38 | |
| 39 | // the undirected graph is connected if we've seen every vertex and |
| 40 | // there is no cycles, which is covered edge count check above. |
| 41 | return len(seen) == n |
| 42 | } |
no outgoing calls