185. Verify Undirected Graph Valid Tree

Verify Undirected Graph Valid Tree

You are given n nodes labeled from 0 to n - 1.

You are also given a list of undirected connections between nodes. Each connection is provided as a string in connections, and each string contains two node labels separated by a comma.

Your task is to determine whether these connections form a valid tree.

A valid tree must satisfy both of the following conditions:

All nodes must be connected, meaning every node can reach every other node by following zero or more connections.
There must be no cycle in the graph.

Since the connections are undirected, the connection "0,1" is the same as "1,0".

Method Signature

boolean validTree(int n, List<String> connections)

Parameters

n: The number of nodes labeled from 0 to n - 1.
connections: A list of strings, where each string is in the format "a,b" and represents an undirected connection between node a and node b.

Returns

Return true if the given connections form a valid tree.
Return false otherwise.

Connection Format

Each connection string contains exactly two integers separated by a comma.
For example, "2,5" means there is an undirected connection between node 2 and node 5.
No connection string will contain the same node twice.
No duplicate connections will be present.
Because the graph is undirected, if "a,b" appears, then "b,a" will not also appear.

Valid Tree Rules

A graph with n nodes is a valid tree only if all n nodes belong to one connected group.
A graph is not a valid tree if it contains any cycle.
A valid tree with n nodes must have exactly n - 1 connections.
A graph with only one node and no connections is a valid tree.

Constraints

1 ≤ n ≤ 3000
0 ≤ connections.size() ≤ n * (n - 1) / 2
Each connection is a string in the format "a,b".
0 ≤ a < n
0 ≤ b < n
a != b
No duplicate connections are present.
No self-loop connections are present.

Examples

Example 1

validTree(n = 5, connections = ["0,1", "0,2", "0,3", "3,4"])
Output: true
Explanation: All nodes are connected, and there is no cycle, so the graph forms a valid tree.

Example 2

validTree(n = 5, connections = ["0,1", "1,2", "2,3", "1,3", "3,4"])
Output: false
Explanation: Nodes 1, 2, and 3 form a cycle, so the graph is not a valid tree.

Example 3

validTree(n = 4, connections = ["0,1", "2,3"])
Output: false
Explanation: The graph has two separate connected groups, so it is not a valid tree.

Example 4

validTree(n = 1, connections = [])
Output: true
Explanation: A single node with no connections forms a valid tree.