Given an undirected graph with n nodes, decide whether it is a tree. A tree must be connected, and it must not contain any cycle.
DSA Animator › DSA Revision › Graph › Is Graph a Tree?
Remember: tree means n minus 1 edges and no cycle. Union find detects a cycle the moment an edge joins a group to itself. The video solves Is Graph a Tree? (GFG, Medium) with the Union Find pattern from the Graph topic, and you can replay every step in the interactive Is Graph a Tree? animation.
Given an undirected graph with n nodes, decide whether it is a tree. A tree must be connected, and it must not contain any cycle.
For 5 nodes with edges 0 1, 0 2, 0 3 and 1 4, the answer is true. Adding the edge 2 3 would create the cycle 0, 2, 3, so the answer would become false.
You could run a search from every node to look for cycles and check connectivity separately. There is a much simpler test.
A tree with n nodes always has exactly n minus 1 edges. So if the edge count is not n minus 1, it cannot be a tree. With exactly n minus 1 edges, it is a tree if and only if there is no cycle. Use union find: for each edge, if both ends already have the same root, that edge closes a cycle. Otherwise, merge the two groups.
There are 5 nodes and 4 edges, so the count is right. Edge 0 1 merges two separate nodes. Edges 0 2 and 0 3 also join new nodes into the group. Edge 1 4 joins node 4, and no edge ever connected two nodes of the same group. No cycle and n minus 1 edges, so the graph is a tree. With the extra edge 2 3, the count is 5, which is already wrong, and 2 and 3 share a root too.
In code, return false if the number of edges is not n minus 1. Create a parent array where every node is its own root. For each edge, find both roots, and return false if they are equal. Otherwise union them, and return true after all edges. With path compression, it's nearly O of n.
Remember: tree means n minus 1 edges and no cycle. Union find detects a cycle the moment an edge joins a group to itself.