🙏

জয়  শ্রী  রাম

🕉

---

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:

• Prerequisite: Union Find Fundamentals

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:

Login to Access Content

Python Solution:

Login to Access Content

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:

Login to Access Content

Python Code:

Login to Access Content

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 .

Instructor: