Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Redundant Connection - I
MEDIUM
15 mins
5 upvotes
Trees
Graph
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Trees
-
-
Graph
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Redundant Connection - I

Contributed by
Dhruv Sharma
Medium
yellow-spark
0/80
Avg time to solve 15 mins
Success Rate 85 %
Share
5 upvotes

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, Constraints, Images )
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
Reset Code
Full screen
Auto
copy-code
Console