• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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.


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.

Code Implementation:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




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 .



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave