Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Graph Valid Tree

Medium
graphunion-findbfsdfs

Given n nodes labeled 0 … n−1 and a list of undirected edges, return true if the edges form a valid tree: connected and acyclic.

Input

  • Line 1: n m
  • Next m lines: u v

Output: true or false.

Example 1
Input:
5 4
0 1
0 2
0 3
1 4
Output:
true
Example 2
Input:
5 5
0 1
1 2
2 3
1 3
1 4
Output:
false

1-2-3 forms a cycle.

Constraints

  • 1 ≤ n ≤ 2000
  • 0 ≤ m ≤ 5000; no duplicate edges.
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.