🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

     0
  /  |  \
 1   2   3
 |
 4

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:

0 -- 1 --  2
     | \  /
     4   3

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false

Solution:

This problem is part of Union-Find Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of Union-Find and become really good at solving problems using Union-Find.

• Prerequisite: Union Find Fundamentals

A valid tree won't have any cycle. So the problem reduces to finding cycle. All the connected nodes would go to same connected component or disjoint set. If there is an edge between two nodes which already belong to same component then that edge would introduce a cycle in that connected component. For more details, please see 4 Ways to Finding Cycles

Union Find would be a very efficient data structure to solve this problem. We would iterate over the given edges array and go on unionizing the connected nodes. At any point of time if we find that we have connectivity between two nodes which have same root (i.e, they belong to the same set) we would know that there is a cycle and return false as this won't be a valid tree.

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Complexity Analysis:

Time Complexity: O(N . Inverse-Ackermann(N)) = O(N) since Inverse-Ackermann(N) = O(1) approximately

Space Complexity: O(N), since we need to store all nodes in the union-find data structure. We would have O(2N) nodes since N edges would have 2 nodes one on each side. So we could have at most 2 * N nodes.
N = number of edges

Please be sure to take a serious look at all the problems discussed in Union Find Problems to become from good to GREAT in solving problems using Union-Find .

Instructor: