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.