Customer Support: email@example.com
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:
- If you are a student, email to firstname.lastname@example.org to get special student discount.
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.
0 / | \ 1 2 3 | 4
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
0 -- 1 -- 2 | \ / 4 3
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
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.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
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:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn