419. Check if a Given Graph Is a Tree

Given an undirected graph with n nodes labeled 0 to n-1 and m edges, print 'Yes' if the graph is a tree (connected, with no cycles) and 'No' otherwise. The first line has n and m; each of the next m lines has an edge as two space-separated node labels.

Input: First line contains the integers n and m. Each of the next m lines contains two space-separated node labels representing an edge. Output: Print 'Yes' if the graph is a tree, otherwise print 'No'.

1 <= n <= 10^5, 0 <= m <= 10^5

Checking the edge count FIRST is a cheap, fast way to reject the overwhelming majority of non-tree graphs before ever running a full traversal - a good example of ordering your checks from cheapest to most expensive.

Given an undirected graph, check whether it's actually a tree - meaning it's fully connected and contains no cycles. Brute force: Check for cycles directly using a full cycle-detection algorithm (like union-find or DFS with parent tracking) AND separately verify connectivity - this works, but doing the cheap edge-count check FIRST can immediately rule out non-trees without even needing the more expensive cycle-detection logic. Optimised: The elegant mathematical fact that 'a graph with n nodes is a tree if and only if it's connected AND has exactly n-1 edges' lets you replace an explicit cycle-detection algorithm with a simple edge COUNT check, combined with just one connectivity check (DFS/BFS) - both together are necessary and sufficient, avoiding more complex cycle-specific logic entirely.

Process the m edges one at a time using a Disjoint Set Union structure: for each edge (u, v), check if u and v are already in the same set - if so, a cycle exists and the graph cannot be a tree. Otherwise, union their sets. After processing all edges, the graph is a tree exactly when no cycle was found and the number of edges equals n - 1 and everything ends up in a single set (full connectivity). This is better than repeated searches because each union/find operation is very fast (near constant time with path compression and union by rank), avoiding a full graph traversal for every edge. Time: O((n + m) * alpha(n)) Space: O(n)

Run a single DFS (or BFS) from node 0, tracking each node's parent in the traversal. Whenever the traversal encounters an edge to an already-visited node that is not the current node's parent, that is a back edge indicating a cycle, so the graph is not a tree. After the traversal finishes, check that all n nodes were visited (connectivity) and that m equals n - 1. This is optimal because it determines both connectivity and acyclicity in one single linear pass over the graph, touching every node and edge exactly once, with none of the repeated work of the other two approaches. Time: O(n + m) Space: O(n)

For every edge added, run a fresh BFS/DFS from one endpoint to check whether the other endpoint is already reachable using only the edges added so far; if it is, adding this edge would create a cycle. Doing this for all m edges, and separately running one more full BFS/DFS to confirm every one of the n nodes is reachable from an arbitrary start node, correctly detects both cycles and disconnection. It is correct because it directly re-verifies reachability from scratch at every step, but repeating a full graph search for every edge makes it expensive. Time: O(m * (n + m)) Space: O(n + m)

1. First, check the EDGE COUNT: a tree with n nodes always has EXACTLY n-1 edges - if the given graph doesn't have exactly n-1 edges, it can't possibly be a tree, answer No immediately. 2. If the edge count matches, verify CONNECTIVITY: run a DFS or BFS from any single node and check that every one of the n nodes gets visited. 3. If both checks pass (exactly n-1 edges AND fully connected), the graph is a tree.

Time: O(n + m) - the edge-count check is O(1), and the connectivity check (DFS/BFS) is linear in the number of nodes and edges. Space: O(n + m), for the adjacency list and the visited-tracking structure used during DFS/BFS.

Test with m not equal to n-1 (answerable as 'No' without even checking connectivity), a single node with m=0 (trivially a tree), a graph with exactly n-1 edges but disconnected with a separate cycle among the extra nodes, and n and m both up to 10^5 for performance.

Be ready to state and briefly justify the underlying theorem (connected + exactly n-1 edges = tree) - this elegant equivalence is exactly what makes the efficient solution possible, and interviewers often want to hear you articulate WHY it holds, not just apply it.