Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Redundant Connection - I

Moderate
0/80
Average time to solve is 15m
8 upvotes
Asked in companies
AdobeIBM

Problem statement

You are given 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 ARR of size NX2. Each element of edges is a pair [u, v] with u < v, which represents an undirected edge connecting nodes u and v.

For the given graph you are required to find an edge that can be removed such that the graph becomes a tree of N nodes.

Example:

 Let’s say we have 3 edges that are {1 , 2} , {1 , 3} and {2 , 3}. So 
 the resulting graph from these edges will be :
      1
     / \
    2 - 3

If we remove the edge {2, 3} then the resulting graph will be a tree with N nodes.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
3 <= N <= 10^3
1 <= ARR[i] <= N

Time Limit: 1 sec
Sample Input 1:
2
3
1 2
1 3
2 3
3
1 2
2 3
1 3
Sample Output 1:
2 3
1 3  
Explanation 1:
For the first test case, 
It is already explained above in the example.

For the second test case, 
Let’s say we have 3 edges that are {1 , 2} , {2 , 3} and {1 , 3}. So 
the resulting graph from these edges will be :
      2
     / \
    1 - 3

So here, unlike the previous example If we remove the edge {1, 3} which is the last occurring edge for the graph above only then the would resulting graph become a tree with N nodes.
Sample Input 2:
2
5
1 2
2 3
3 4
1 4
1 5
4
1 2
1 3
3 4
1 4
Sample Output 2:
 1 4
 1 4
Full screen
Console