Leetcode 684. Redundant Connection
Problem Description
Given a graph, we are required to find and remove an extra edge that makes the graph a tree. A tree in computer science is considered an undirected graph that is connected and has no cycles. An undirected graph means a set of objects which are connected together, where all the edges are bidirectional. A graph with no cycles means that there is no closed path in the graph.
The input to the problem will be a 2D-array where each nested list represents an edge of the graph. Our task is to return an edge that can be removed so that the resulting graph is a tree.
Let's look at the first example, where we have a graph represented as the following 2D-array: [[1,2], [1,3], [2,3]]. The graph will look like this:
1 1 2 / \ 32 - 3
In this case, removing edge [2,3] or [1,3] will give us a tree. However, since the problem statement asks us to return the answer that occurs last in the 2D-array, we will return [2,3]
Solution Approach
The solution to this problem lies in a data structure called "Disjoint Sets" and an algorithm called "Union-Find". This is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. Union-Find algorithms are used to find whether an element is a direct child or a grandchild of another element.
For this problem, we will go through every edge in the 2D array, and for each edge, we will use the Union-Find algorithm to find whether the two nodes of the edge are already in the same set. If they are, it means these two nodes are already connected and the edge is extra, hence return this edge. If they are not in the same set, we union the two nodes (add to the same set). We do this until we find the first redundant connection.
Our time complexity for the solution is O(n), because we go through every edge in the 2D array once.
Python Solution
1 2python 3class Solution: 4 def findRedundantConnection(self, edges): 5 parent = [0] * len(edges) 6 7 def find(x): 8 if parent[x] == 0: 9 return x 10 parent[x] = find(parent[x]) 11 return parent[x] 12 13 def union(x, y): 14 rootX = find(x) 15 rootY = find(y) 16 if rootX == rootY: 17 return False 18 parent[rootX] = rootY 19 return True 20 21 for x, y in edges: 22 if not union(x - 1, y - 1): 23 return [x, y]
In the python solution, for each edge, we're trying to merge the two nodes from the edge. If they are already in the same set, return the edge as it is the redundant one.
Java Solution
1
2java
3public int[] findRedundantConnection(int[][] edges) {
4 int[] parent = new int[1001];
5 for (int i = 0; i < parent.length; i++) parent[i] = i;
6 for (int[] edge : edges) {
7 int from = edge[0], to = edge[1];
8 if (find(parent, from) == find(parent, to)) return edge;
9 else parent[find(parent, to)] = find(parent, from);
10 }
11 return new int[2];
12}
13
14// helper function to return the ultimate parent
15private int find(int[] parent, int x) {
16 if (x != parent[x]) parent[x] = find(parent, parent[x]);
17 return parent[x];
18}
In the Java solution, we similarly do the same thing as in Python. Our ultimate goal is to iteratively merge sets until we hit a case where two nodes belong to the same set which will be our answer.
JavaScript Solution
1 2javascript 3var findRedundantConnection = function(edges) { 4 const parents = Array(edges.length + 1).fill(-1); 5 for (let edge of edges) { 6 if (!union(edge[0], edge[1])) { 7 return edge; 8 } 9 } 10 11 function find(node) { 12 let parent = parents[node]; 13 while (parent > 0) { 14 parent = parents[parent]; 15 } 16 return node; 17 } 18 19 function union(node1, node2) { 20 const parent1 = find(node1); 21 const parent2 = find(node2); 22 if (parent1 === parent2) return false; 23 parents[parent1] += parents[parent2]; 24 parents[node2] = node1; 25 return true; 26 } 27};
For the JavaScript solution, we are using union-by-size, meaning each root node is assigned a size (parent[rootNode] = size), and during a union operation, the smaller tree is attached to the larger tree.
C++ Solution
1
2cpp
3class Solution {
4public:
5 vector<int> findRedundantConnection(vector<vector<int>>& edges) {
6 vector<int> p(2001, 0);
7 for (int i = 0; i < p.size(); ++i) p[i] = i;
8 for (auto v : edges) {
9 int n1 = v[0], n2 = v[1];
10 while (n1 != p[n1]) n1 = p[n1];
11 while (n2 != p[n2]) n2 = p[n2];
12 if (n1 == n2) return v;
13 else p[n1] = n2;
14 }
15 return {};
16 }
17};
The C++ solution uses similar steps but also uses the power of C++ language features to make it more compact and clean.
C# Solution
1
2csharp
3public int[] FindRedundantConnection(int[][] edges) {
4 var parents = new int[2000];
5 for(var i = 0; i < parents.Length ; i++) parents[i] = i;
6
7 foreach(var edge in edges){
8 var f = edge[0];
9 var t = edge[1];
10 if(find(f, parents) == find(t, parents)) return edge;
11 else parents[find(f, parents)] = find(t, parents);
12 }
13
14 return new int[]{};
15}
16
17public int find(int node, int[] parents){
18 if(parents[node] != node)
19 parents[node] = find(parents[node], parents);
20 return parents[node];
21}
The C# solution behaves the same as the Java solution. It uses arrays to keep track of node parents and does union and find operations on them. A helper function "find" is used to find the ultimate parent of a given node.## Ruby Solution
1 2ruby 3class UnionFind 4 attr_accessor :parent 5 6 def initialize(size) 7 self.parent = Array.new(size) { |i| i } 8 end 9 10 def find(x) 11 return x if parent[x] == x 12 parent[x] = find(parent[x]) 13 parent[x] 14 end 15 16 def union(x, y) 17 root_x = find(x) 18 root_y = find(y) 19 return false if root_x == root_y 20 parent[root_x] = root_y 21 return true 22 end 23end 24 25def find_redundant_connection(edges) 26 union_find = UnionFind.new(edges.size + 1) 27 28 edges.each do |x, y| 29 return [x, y] unless union_find.union(x,y) 30 end 31end
The Ruby solution makes use of Object-Oriented Programming (OOP) and has defined a class UnionFind
which exposes methods find()
and union()
.
In the method find_redundant_connection(edges)
, an object of the UnionFind
class is created which is then utilized to perform union-find operations on the graph edges.
Conclusion
The union-find algorithm is a powerful tool for solving the given problem of finding and removing an extra edge that makes the graph a tree. It can be effectively implemented in variety of popular programming languages such as Python, Java, Javascript, C++, C#, and Ruby. By understanding the problem and applying the appropriate algorithmic approach, we can arrive at a concise and optimum solution.
It's also important to remember that implementation may vary according to language-specific optimizations, but the core logic remains the same. Appropriate data structures are selected to support required operations while ensuring a balance between readability, scalability and performance. If you apply a similar approach to problems in your domain, you'll be on your way to achieving efficient solutions.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.