All problems

Graph Valid Tree

Medium · graph traversal

A small office has n computers, numbered 0 to n - 1. The list edges holds the network cables, each a pair [a, b] meaning computer a is connected to computer b. A cable works in both directions.

The network is well designed if it forms exactly one tree: every computer can reach every other computer through the cables, and there is no way to travel along cables and come back to where you started without reusing a cable. Return True if the network is well designed and False otherwise.

The same pair may appear more than once, and a pair may connect a computer to itself. Neither of those counts as a tree.

Examples

Example 1

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

Output: True

Every computer is reachable from computer 0 and there is exactly one route between any two.

Example 2

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

Output: False

Computers 1, 2 and 3 are joined in a ring, so there is a loop.

Example 3

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

Output: False

Computers 0 and 1 cannot reach computers 2 and 3, so the network is split in two.

Constraints