Graph Valid Tree

mediumFREEGraphsBlind 75

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

Input

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

Output

True

Reasoning

n is 5, so the nodes are labelled 0 to 4. edges lists 4 undirected connections: $(0,1), (0,2), (0,3), (1,4)$ . Each pair links its two nodes in both directions.
A tree on $n$ nodes always has exactly $n-1$ edges: fewer leaves some node cut off, more forces a cycle. Here $n - 1 = 5 - 1 = 4$ , 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, $(0,1), (1,2), (2,3), (1,3), (1,4)$ , contain the loop $1 \to 2 \to 3 \to 1$ and give False, while a single node with no edges is a valid tree, since $1 - 1 = 0$ .

Constraints

1 <= n <= 2000
0 <= number of edges <= 5000

Learn this in

Advanced Data StructuresDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

To tackle the "Graph Valid Tree" problem, it's essential to understand the fundamental concepts of graph theory. A graph is a non-linear data structure consisting of nodes (also known as vertices) and edges that connect these nodes. In the context of this problem, we're dealing with an undirected graph, where edges do not have a direction and can be traversed in both ways. A valid tree is a special type of graph that is connected (there is a path between every pair of nodes) and acyclic (contains no cycles).

The concept of connectedness is crucial in this problem. A graph is considered connected if there is a path between every pair of nodes. This can be checked using graph traversal algorithms such as Depth-First Search (DFS) or Breadth-First Search (BFS). On the other hand, cycles in a graph refer to a path that starts and ends at the same node, passing through at least one edge more than once. The absence of cycles is a necessary condition for a graph to be considered a tree.

Understanding the relationship between the number of nodes and edges in a tree is also vital. In a valid tree with $n$ nodes, there are exactly $n-1$ edges. This is because each edge added to the graph connects two previously disconnected components, and $n-1$ edges are required to connect $n$ nodes without forming any cycles. This relationship can be expressed as $e = n - 1$ , where $e$ is the number of edges and $n$ is the number of nodes.

Algorithm/Approach

The general approach to solving this type of problem involves checking the two necessary conditions for a graph to be a valid tree: connectedness and acyclicity. This can be achieved by using graph traversal algorithms such as DFS or BFS to traverse the graph and detect any cycles. Additionally, the relationship between the number of nodes and edges can be used to quickly identify if the graph is a valid tree.

Step-by-Step Strategy

To implement the solution, follow these steps:

Read the input and create an adjacency list representation of the graph.
Check if the number of edges is equal to $n-1$ , where $n$ is the number of nodes. If not, the graph is not a valid tree.
Use a graph traversal algorithm (such as DFS or BFS) to traverse the graph and detect any cycles.
If the graph is traversed completely without detecting any cycles, and the number of edges is $n-1$ , then the graph is a valid tree.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly handling the case where the input graph is disconnected.
Failing to detect cycles in the graph.
Not checking the relationship between the number of nodes and edges.

Time & Space Complexity

The expected time complexity for this problem is $O(n + e)$ , where $n$ is the number of nodes and $e$ is the number of edges. This is because we need to traverse the graph once to detect any cycles and check the connectedness. The space complexity is $O(n + e)$ as well, as we need to store the adjacency list representation of the graph.

solution.py

Python 3.13

Test results