Graph Valid Tree

Medium

The problem

A graph has n nodes numbered 0 to n - 1, and each pair [a, b] in edges is a two-way connection. Return true if the graph is a tree: every node can reach every other node, and there are no cycles. Otherwise return false.

Example 1
Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true
All five nodes are connected and there is no loop.
Example 2
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false
Nodes 1, 2 and 3 form a loop.
Example 3
Input: n = 4, edges = [[0, 1], [2, 3]]
Output: false
Nodes 0, 1 cannot reach nodes 2, 3.

Limits

1 ≤ n ≤ 2,000
0 ≤ len(edges) ≤ 5,000
There are no repeated edges

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

A tree on n nodes has exactly n−1 edges and is fully connected.

The idea

Check edges == n−1, then confirm connectivity with DFS/BFS or that union-find never finds a cycle.

Target: O(V + E) time

Go function shape

func validTree(n int, edges [][]int) bool

Reference solution

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

// ValidTree: n nodes form a tree if there are exactly n-1 edges and no edge closes a cycle.
func ValidTree(n int, edges [][]int) bool {
	if len(edges) != n-1 {
		return false
	}
	u := NewUF(n)
	for _, e := range edges {
		if !u.Union(e[0], e[1]) {
			return false
		}
	}
	return true
}

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