1. You are given 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.
2. The 2D array 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.
3. You have to find 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.
4. For example,
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
Notes:
1. TreeNode class represents the node of a Binary tree.
2. display is a utility function which displays the contents of a binary tree, feel free to use it for debugging purposes.
3. main takes input from the users.
4. This is a functional problem.
5. You have to complete the function findRedundantConnection. It takes as input a 2D array of edges. It should return an array containing the edge to be removed.
6. Don't change the code of TreeNode, main, display and other utility functions.Input Format
First line takes input N, denoting the length of the 2D array of edges. Next N lines take input 2 space separated integers representing the edges. Input is handled for you.
Output Format
The edge to be removed. Output is handled for you.
Constraints
N/A
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
5 1 2 2 3 3 4 1 4 1 5
Output
1 4