Graph Valid Tree
MediumGraphs
You have n nodes labelled 0 to n - 1 and a list of undirected edges, where edges[i] = [a, b] connects nodes a and b.
Return True if these edges make the nodes a valid tree, and False otherwise. A valid tree is:
- connected: every node can be reached from every other node, and
- acyclic: there is no cycle, so there is exactly one path between any two nodes.
A single node with no edges is a valid tree.
Example 1
- Input:
- n = 6, edges = [[0, 1], [1, 2], [1, 3], [3, 4], [3, 5]]
- Output:
- True
- Explanation
- Starting from node 0 you can reach all six nodes, and the five edges never close a loop, so this is a tree.
Example 2
- Input:
- n = 5, edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
- Output:
- False
- Explanation
- There are 4 edges for 5 nodes, the right count for a tree, but nodes 2, 3 and 4 form a cycle and nodes 0 and 1 are cut off from them. Counting edges alone is not enough.
Example 3
- Input:
- n = 4, edges = [[0, 1], [2, 3]]
- Output:
- False
- Explanation
- No cycle exists, but the graph is in two pieces ({0, 1} and {2, 3}), so it is not connected.
Constraints
1 <= n <= 20000 <= edges.length <= 5000edges[i].length == 20 <= a, b < nanda != b- There are no repeated edges