Graph Valid Tree

if i in visit:

Check if current node has already been visited.

Encountering a visited node during DFS (other than the parent) indicates a cycle, so returning false here detects cycles early.

if j == prev:

Skip the neighbor if it is the previous node.

Ignoring the edge back to the parent prevents false cycle detection caused by bidirectional edges in undirected graphs.

return dfs(0, -1) and n == len(visit)

Return true if DFS from node 0 found no cycles and all nodes were visited.

Combining cycle detection with connectivity check ensures the graph is a valid tree, as both conditions are necessary and sufficient.

adj[n1].append(n2)

Add second node to the adjacency list of the first node.

Adding edges in both directions reflects the undirected nature of the graph, which is critical for correct traversal.

adj[n2].append(n1)

Add first node to the adjacency list of the second node.

This symmetric addition ensures that the graph representation correctly models undirected edges, preventing traversal errors.

return False

Return false upon cycle detection.

This immediate return prunes the search and signals that the graph is not a valid tree due to a cycle.

if not dfs(j, i):

Recursively call DFS on neighbor node.

Recursion explores deeper nodes, enabling full traversal and cycle detection in the graph.

return False

Return false if a cycle is detected in recursion.

Propagating the false return up the call stack ensures that any detected cycle invalidates the entire graph.

adj = {i: [] for i in range(n)}

Initialize adjacency list with empty lists for each node.

Creating an adjacency list for all nodes ensures that even isolated nodes are represented, enabling accurate traversal and connectivity checks.

visit = set()

Initialize a set to track visited nodes.

The visited set prevents revisiting nodes, which is crucial for cycle detection and connectivity verification.

def dfs(i, prev):

Define DFS function with current node and previous node parameters.

Passing the previous node allows the DFS to distinguish between a legitimate back edge and the edge leading to the parent, preventing false cycle detection.

visit.add(i)

Mark current node as visited.

Recording the current node as visited prevents infinite loops and supports connectivity checks after traversal.

continue

Continue to next neighbor if it is the parent.

This skip maintains correct cycle detection logic by not treating the parent edge as a cycle.

return True

Return true if no cycles found in neighbors.

Returning true indicates the current path is acyclic, allowing DFS to continue exploring other branches.

if not n:

Check if the number of nodes is zero.

An empty graph with zero nodes is trivially a valid tree, so returning true immediately handles this edge case efficiently.

for n1, n2 in edges:

Iterate over each edge to populate adjacency list.

Processing each edge to build the graph representation is essential for enabling efficient neighbor lookups during DFS.

for j in adj[i]:

Iterate over neighbors of the current node.

Exploring all adjacent nodes is necessary to traverse the entire connected component and detect cycles.

return True

Return true for empty graph.

This early return prevents unnecessary processing and clarifies the function's behavior for empty input.