Graph Valid Tree
Given n nodes (0 to n-1) and a list of undirected edges, check if these edges form a valid tree (connected, no cycles).
Implement valid_tree(n, edges), where n is an integer and edges is a list of [u, v] pairs (an empty list when there are no edges). Return True if the edges form a valid tree, otherwise False.
Example
5 0:1,0:2,0:3,1:4
True
nis5, so the nodes are labelled 0 to 4.edgeslists 4 undirected connections: . Each pair links its two nodes in both directions.- A tree on nodes always has exactly edges: fewer leaves some node cut off, more forces a cycle. Here , and there are exactly 4 edges, so the count is right.
- The count alone is not enough; the edges must also reach every node. Node 0 touches nodes 1, 2 and 3 directly, and node 4 hangs off node 1. All 5 nodes sit in one connected piece.
- Four edges joining five nodes into a single piece leave no spare edge, so no cycle can exist. The answer is
True. - Notice how the other cases differ: 5 edges on 5 nodes, , contain the loop and give
False, while a single node with no edges is a valid tree, since .
Constraints
- 1 <= n <= 2000
- 0 <= edges.length <= 5000