Skip to content
BASA DSA

Graph Valid Tree

MediumGraphs

Return whether the undirected graph on n nodes labeled 0..n-1 is a tree: connected and acyclic.

Example 1

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 0, node 1: 1, node 2: 2, node 3: 3. Edges: node 0 (0) — node 1 (1); node 1 (1) — node 2 (2); node 1 (1) — node 3 (3).0123
Undirected input edges; isolated vertices are included.

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

Explanation

Four nodes connect through three edges without a cycle.

Example 2

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 0, node 1: 1, node 2: 2. Edges: node 0 (0) — node 1 (1); node 1 (1) — node 2 (2); node 2 (2) — node 0 (0).012
Undirected input edges; isolated vertices are included.

Input
n = 3
edges = [[0,1],[1,2],[2,0]]
Output
false

Explanation

Three edges form a cycle, violating the tree requirement.

Example 3

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 0, node 1: 1, node 2: 2. Edges: node 0 (0) — node 1 (1).012
Undirected input edges; isolated vertices are included.

Input
n = 3
edges = [[0,1]]
Output
false

Explanation

Node 2 is disconnected from nodes 0 and 1.

Example 4

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 0. Edges: none.0
Undirected input edges; isolated vertices are included.

Input
n = 1
edges = []
Output
true

Explanation

A single node is connected to itself and has no cycle, so it is a tree.

Constraints

  • 1 <= n <= 2000
  • Edges are distinct valid unordered pairs without self-loops

Function contractvalidTreeArguments: json, json
Loading draft…
SolutionRuns on your device