Data Structures19 sections · 729 units
Open in Course

Problem - Graph Valid Tree

Tree = connected + acyclic

Given nn nodes and a list of undirected edges, check if these edges form a valid tree. A valid tree must be:

1.1. Connected (one component)

2.2. Acyclic (exactly n1n-1 edges) Example: n=5n = 5, edges =[[0,1],[0,2],[0,3],[1,4]]= [[0,1],[0,2],[0,3],[1,4]] is a tree. n=5n = 5, edges =[[0,1],[1,2],[2,3],[1,3],[1,4]]= [[0,1],[1,2],[2,3],[1,3],[1,4]] is not (has a cycle). Constraints: nn from 11 to 20002000, edges from 00 to 50005000.