Graph Valid TreeMedium

Graph Valid Tree

Medium 4.1k48% acceptance

GraphUnion FindDepth-First SearchBreadth-First Search

You are given n nodes labeled 0 to n - 1 and a list of undirected edges. Return true if these edges form a valid tree.

A graph is a valid tree exactly when it is fully connected (every node is reachable) and contains no cycle. Equivalently: it is connected and has exactly n - 1 edges.

Example 1

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Output: true

4 edges over 5 nodes, all connected, no cycle — a tree.

Example 2

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

Output: false

The edges 1-2, 2-3, 1-3 form a cycle, so it is not a tree.

Example 3

Input: n = 1, edges = []

Output: true

Constraints

1 ≤ n ≤ 2000
0 ≤ edges.length ≤ 5000
No self-loops or duplicate edges; 0 ≤ a, b < n.

Asked atGoogleMetaAmazonZenefits

JavaScript

⌘↵ to run

Loading editor…

Case 1

5, [[0,1],[0,2],[0,3],[1,4]]

expected: true

Case 2

5, [[0,1],[1,2],[2,3],[1,3],[1,4]]

expected: false

Case 3

1, []

expected: true

Case 4

2, []

expected: false

Case 5

4, [[0,1],[2,3]]

expected: false

Case 6

3, [[0,1],[1,2],[2,0]]

expected: false

Case 7

4, [[0,1],[1,2],[2,3]]

expected: true