Redundant Connection
Application of Union Find / Disjoint Set Union Data Structure

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
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 2Darray 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 2Darray. The answer edge [u, v] should be in the same format, with u < v.
The size of the input 2Darray will be between 3 and 1000.
Every integer represented in the 2Darray 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 UnionFind Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of UnionFind and become really good at solving problems using UnionFind.
Please have a very good understanding of UnionFind 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 UnionFind based solution for even a complex problem when you are familiar with the implementation of UnionFind data structure discussed in the Template section of UnionFind Fundamentals chapter.
Solution:
 Prerequisite: Union Find Fundamentals
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 InverseAckermann 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 UnionFind Fundamentals chapter.
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Complexity Analysis:
Time Complexity: O(N . InverseAckermann(N)) = O(N), since O(InverseAckermann(N)) = O(1) approximately, as discussed in UnionFind Fundamentals.Space Complexity: O(N) since we need to store all nodes in the unionfind 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
UnionFind .
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.