Solution: Redundant Connection

Let's solve the Redundant Connection problem using the Union Find pattern.

We'll cover the following

Statement

We’re given an undirected graph consisting of nn nodes. The graph is represented as an array called edges, of length nn, where edges[i] = [a, b] indicates that there is an edge between nodes a and b in the graph.

Return an edge that can be removed to make the graph a treeA tree is an undirected graph that is connected and has no cycles. of nn nodes. If there are multiple candidates for removal, return the edge that occurs last in edges.

Constraints:

  • 3≤3 \leq nn ≤100\leq 100
  • edges.length== nn
  • edges[i].length == 2
  • 1≤1 \leq a << b ≤n\leq n
  • a≠ba \neq b
  • There are no repeated edges.
  • The given graph is connected.
  • The graph contains only one cycle.

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

We can solve this problem using techniques like DFS or BFS, however, the naive approach using DFS or BFS has a time complexity of O(n2)O(n^2) in the worst-case scenario. This is because the DFS or BFS algorithm will explore the graph by visiting each node and its edges, which may result in visiting many nodes multiple times, and not necessarily finding the redundant connection in an efficient manner.

Optimized approach using union find

We can use the union find pattern which is known to detect cycles within a graph efficiently. We iterate through the given edges of the graph. For each edge, we check if its two nodes are already connected in the union find structure using the find method. If they're not connected, we connect the two nodes using the union by rank method. If they are connected, adding this edge would create a cycle, and thus, it's the redundant connection we're looking for, so we return it.

The slides below illustrate how the algorithm runs:

Press + to interact
canvasAnimation-image
1 of 10

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step by step solution construction

We start with the basic implementation of Union Find (without the use of rank or path compression):

File: UnionFind.java

In the UnionFind class, we declare the parent array with length based on the edges array.

File: main.java

In the redundantConnection function, we’ll declare an object of the given class and initialize the parent array with default values.

main.java
UnionFind.java
import java.util.*;
class UnionFind {
    public int[] parent;
    // Constructor
    public UnionFind(int n) {
        
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }
    // Function to find which subset a particular element belongs to
    public int find(int v) {
        if (parent[v] != v) {
            return find(parent[v]);
        }
        return v;
    }
    // Function to join two subsets into a single subset
    public void union(int v1, int v2) {
    
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 != p2) {
            parent[p1] = p2;;
        }   
    }
}
Redundant Connection

File: UnionFind.java

Next, we need to check if the vertices forming an edge have the same parent. In the union function, we’ll call the parent of the first vertex p1 and the parent of the second vertex p2. The algorithm is described as follows:

  • If both v1 and v2 have the same parent, i.e., p1 is equal to p2, the given edge is redundant, so we return FALSE.

  • Otherwise, this edge is connecting two vertices that were not already connected. So, we’ll update the parent list by making a connection based on the current edge and then return TRUE.

File: main.java

In the redundantConnection function, we traverse the edges array and for each edge, we attempt to connect its two vertices, v1, and v2, through the union(v1, v2) method.

main.java
UnionFind.java
import java.util.*;
class UnionFind {
    public int[] parent;
    // Constructor
    public UnionFind(int n) {
        
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }
    // Function to find which subset a particular element belongs to
    // Returns FALSE if both vertices have the same parent, otherwise, updates the parent and rank lists by making a connection based on the passed edge
    // Returns TRUE if no cycle exits in the graph
    public int find(int v) {
        if (parent[v] != v) {
            return find(parent[v]);
        }
        return v;
    }
    // Function to join two subsets into a single subset
    public boolean union(int v1, int v2) {
        
        System.out.println("\n\n\tChecking if the vertices have the same parent");
        System.out.println("\t\tEdge: [" + v1 + ", " + v2 + "]");
        System.out.println("\t\tFirst vertex: " + v1);
        System.out.println("\t\tSecond vertex: " + v2);
        // Find the root parents of v1 and v2
        int p1 = find(v1);
        int p2 = find(v2);
        System.out.println("\t\t\tParent of the first vertex: " + p1);
        System.out.println("\t\t\tParent of the second vertex: " + p2);
        // If both parents are the same, a cycle exists and v1,v2 is the redundant edge
        if (p1 == p2) {
            System.out.println("\t\tSince both vertices have the same parent, this is a redundant edge");
            return false;
        } 
        
        // Updates the parent list otherwise 
        else {
            System.out.println("\t\tThe vertices don't have the same parent, updating parent array");
            System.out.print("\t\t\tparent: " + Arrays.toString(parent) + " ⟶ ");
            parent[p1] = p2;;
            System.out.println(Arrays.toString(parent));
        } 
        return true;
    }
}
Redundant Connection

We will now update the Union Find algorithm by adding both union by rank and path compression methods. We’ll make the following changes to the UnionFind class:

Union by rank:

  • We initialize a rank array (set to the length of the edges array) with 11s.

  • In the union function, if the parents, p1 and p2 of the vertices are not the same, we make the connection based on the ranks of both parents. This is done in the following way:

    • If p1's rank is greater than p2's rank, we’ll update p2's parent with p1, and add p2's rank to p1's rank. For example, if rank[p1] =5= 5 and rank[p2] =2= 2, we’ll add p2 to p1's set and update its rank to 5+2=75 + 2 = 7.

    • Similarly, if p2's rank is greater than p1's rank, we’ll update p1's parent with p2, and add p1's rank to p2's rank.

Path compression:

  • In the find function, for a node v, we make the found root as the parent of v so that we don’t have to traverse all the intermediate nodes again on further find operations.
main.java
UnionFind.java
import java.util.*;
class UnionFind {
    public int[] parent;
    public int[] rank;
    // Constructor
    public UnionFind(int n) {
        
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    // Function to find which subset a particular element belongs to
    // Returns FALSE if both vertices have the same parent, otherwise, updates the parent and rank lists by making a connection based on the passed edge
    // Returns TRUE if no cycle exits in the graph
    public int find(int v) {
        if (parent[v] != v) {
            parent[v] = find(parent[v]);
        }
        return parent[v];
    }
    // Function to join two subsets into a single subset
    public boolean union(int v1, int v2) {
        
        System.out.println("\n\n\tChecking if the vertices have the same parent");
        System.out.println("\t\tEdge: [" + v1 + ", " + v2 + "]");
        System.out.println("\t\tFirst vertex: " + v1);
        System.out.println("\t\tSecond vertex: " + v2);
        // Find the root parents of v1 and v2
        int p1 = find(v1);
        int p2 = find(v2);
        System.out.println("\t\t\tParent of the first vertex: " + p1);
        System.out.println("\t\t\tParent of the second vertex: " + p2);
        // If both parents are the same, a cycle exists and v1,v2 is the redundant edge
        if (p1 == p2) {
            System.out.println("\t\tSince both vertices have the same parent, this is a redundant edge");
            return false;
        } 
        
        // Updates the parent and rank lists otherwise 
        else if (rank[p1] > rank[p2]) {
            System.out.println("\t\tThe vertices don't have the same parent, updating parent and rank arrays");
            System.out.print("\t\t\tparent: " + Arrays.toString(parent) + " ⟶ ");
            parent[p2] = p1;
            System.out.println(Arrays.toString(parent));
            System.out.print("\t\t\trank: " + Arrays.toString(rank) + " ⟶ ");
            rank[p1] += rank[p2];
            System.out.println(Arrays.toString(rank));
        } 
        
        else {
            System.out.println("\t\tThe vertices don't have the same parent, updating parent and rank arrays");
            System.out.print("\t\t\tparent: " + Arrays.toString(parent) + " ⟶ ");
            parent[p1] = p2;
            System.out.println(Arrays.toString(parent));
            rank[p2] += rank[p1];
            System.out.print("\t\t\trank: " + Arrays.toString(rank) + " ⟶ ");
            System.out.println(Arrays.toString(rank));
        }
        return true;
    }
}
Redundant Connection

Lastly, we need to return the redundant edge. While traversing the edges array, for each edge, we will check if the union(v1, v2) method returns FALSE:

  • If it does, both v1 and v2 will have the same parent. So the current edge will be redundant, and we return it.

  • Otherwise, v1 and v2 have different parents, so we connect them.

main.java
UnionFind.java
import java.util.*;
class RedundantConnections {
    
    public static int[] redundantConnection(int[][] edges) {
        // Declaring the parent and rank list with lengths based on the edges array
        System.out.println("\n\tDeclaring the parent and rank arrays");
        UnionFind connections = new UnionFind(edges.length);
        System.out.println("\t\tparent: " + Arrays.toString(connections.parent));
        System.out.println("\t\trank: " + Arrays.toString(connections.rank));
        // Traversing the edges of the graph to check for the redundant edge
        for (int[] edge : edges) {
            int v1 = edge[0];
            int v2 = edge[1];
            if (!connections.union(v1, v2)) {
                return edge;
            }
        }
        return new int[]{};
    }
    // Driver code
    public static void main(String[] args) {
        int[][][] edges = {
                {{1, 2}, {1, 3}, {2, 3}},
                {{1, 2}, {2, 3}, {1, 3}},
                {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}},
                {{1, 2}, {1, 3}, {1, 4}, {3, 4}, {2, 4}},
                {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}}
        };
        for (int i = 0; i < edges.length; i++) {
            System.out.println((i + 1) + ".\tEdges: " + Arrays.deepToString(edges[i]));
            System.out.println("\n\tThe redundant connection in the graph is: " + Arrays.toString(redundantConnection(edges[i])));
            System.out.println(new String(new char[100]).replace("\0", "-"));
        }
    }
}
Redundant Connection

Just the code

Here's the complete solution to this problem:

main.java
UnionFind.java
import java.util.*;
class RedundantConnections {
    
    public static int[] redundantConnection(int[][] edges) {
        UnionFind connections = new UnionFind(edges.length);
        for (int[] edge : edges) {
            int v1 = edge[0];
            int v2 = edge[1];
            if (!connections.union(v1, v2)) {
                return edge;
            }
        }
        return new int[]{};
    }
    // Driver code
    public static void main(String[] args) {
        int[][][] edges = {
                {{1, 2}, {1, 3}, {2, 3}},
                {{1, 2}, {2, 3}, {1, 3}},
                {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}},
                {{1, 2}, {1, 3}, {1, 4}, {3, 4}, {2, 4}},
                {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}}
        };
        for (int i = 0; i < edges.length; i++) {
            System.out.println((i + 1) + ".\tEdges: " + Arrays.deepToString(edges[i]));
            System.out.println("\n\tThe redundant connection in the graph is: " + Arrays.toString(redundantConnection(edges[i])));
            System.out.println(new String(new char[100]).replace("\0", "-"));
        }
    }
}
Redundant Connection

Solution summary

To recap, the solution to this problem can be divided into the following two main parts:

  • Initialize parent and rank arrays based on the length of the edges array.

  • Traverse the edges array and for each edge, compare the parents of both vertices:

    • If the parents are the same, the current edge is redundant, so we return it.

    • Otherwise, we connect the two vertices based on their respective ranks.

Time complexity

The time complexity of this solution is O(n)O(n), where nn is the number of edges.

Explanation:

  • We use a loop to traverse the edges array, resulting in O(n)O(n) iterations.

  • The time complexity of the the Union and Find functions is O(α(n))O( \alpha (n)), since both path compression and union find by rank are being used. α(n)\alpha (n) is almost constant time and grows very slowly with the input size, so the time complexity of both these functions can be considered as constant time for practical purposes.

Therefore, the overall time complexity becomes O(n×α(n))O(n \times \alpha (n)), which simplifies to O(n)O(n).

Space Complexity

The space complexity of this solution is O(n)O(n).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.