261. Graph Valid Tree

Medium
Depth-First Search
Breadth-First Search
Union Find
Graph

Description

From doocs/leetcode

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

 

Example 1:

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

Example 2:

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

 

Constraints:

    • 1 <= n <= 2000
    • 0 <= edges.length <= 5000
    • edges[i].length == 2
    • 0 <= ai, bi < n
    • ai != bi
    • There are no self-loops or repeated edges.

Hints

Hint 1
Given <code>n = 5</code> and <code>edges = [[0, 1], [1, 2], [3, 4]]</code>, what should your return? Is this case a valid tree?
Hint 2
According to the <a href="https://en.wikipedia.org/wiki/Tree_(graph_theory)" target="_blank">definition of tree on Wikipedia</a>: “a tree is an undirected graph in which any two vertices are connected by <i>exactly</i> one path. In other words, any connected graph without simple cycles is a tree.”

Statistics

Acceptance
49.7%
Submissions
1,039,100
Accepted
516,900