• 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.



Problem Statement:


In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.


The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3


Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3


Note: 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.

Please have a very good understanding of Union-Find Fundamentals before solving this problem. Through all the problems discussed in Problem Solving using Union Find one of my goals is to show you how easy it becomes writing an Union-Find based solution for even a complex problem when you are familiar with the implementation of Union-Find data structure discussed in the Template section of Union-Find Fundamentals chapter.

Solution:


Please read the chapter 4 Ways to Finding Cycles to have a very good understanding of finding cycles in a graph, since we would need that knowledge to solve this problem.

If you read the problem statement carefully you would figure that the problem statement is actually asking us to find the edge that is introducing a cycle in the graph and remove that so that there is no cycle.

Using Union Find data structure is a very efficient way to find cycle. For every two nodes connected to each other we unionize them. While processing an edge if we find that the two nodes of the edge belong to same connected component or set (i.e, they have same root) we would know that that is the edge that is going to introduce a cycle and would return that edge as output.

Java Solution:




This is a Premium content.
Please subscribe to Algorithms course to access the code.




Python Solution:




This is a Premium content.
Please subscribe to Algorithms course to access the code.





Complexity Analysis:

  • Time Complexity: O(Nα(M)), where N is the number of edges and M is the number of vertices in the given graph, and α is the Inverse-Ackermann function. We make up to N union operations and each of these operations takes amortized O(α(N)) time. In Union Find Fundamentals chapter we have seen O(α(N)) is approximately O(1). So, O(Nα(M)) = O(N). Therefore, overall time complexity = O(N).


Solution using our Union Find Template Code:


The template code is discussed in details in Union-Find Fundamentals chapter.

Java Code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.




Python Code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Complexity Analysis:

Time Complexity: O(N . Inverse-Ackermann(N)) = O(N), since O(Inverse-Ackermann(N)) = O(1) approximately, as discussed in Union-Find Fundamentals.
Space Complexity: O(N) since we need to store all nodes in the union-find data structure and number of nodes = O(2N).
N = total 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