📘

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).

Input: first line = n, second = edges as u:v comma-separated (or 'none').

Input:

5
0:1,0:2,0:3,1:4

Output:

True

Reasoning:

The input 5 represents the number of nodes in the graph, and the edges are given as 0:1,0:2,0:3,1:4, which can be represented as a list of pairs: (0,1), (0,2), (0,3), (1,4).
We can use a union-find algorithm or depth-first search (DFS) to check if the graph is connected and has no cycles. In this case, a DFS traversal starting from node 0 visits all nodes (0, 1, 2, 3, 4), indicating the graph is connected.
The number of edges in a tree with $n$ nodes is $n-1$ , and since there are $4$ edges and $5$ nodes, the condition is met: $n-1 = 5-1 = 4$ .
Since the graph is connected and has $n-1$ edges, it forms a valid tree, so the output is True.

Editor

Python 3.13.1

0/0

Run code to see test results.

📘