684. Redundant Connection

MediumDepth-First SearchBreadth-First SearchUnion FindGraph
Leetcode Link

Problem Description

In this problem, we're given a graph that was a tree initially, but an additional edge was added to it. An edge in this context is represented by a pair of nodes that it connects, given as [a, b]. Since a proper tree has no cycles and is connected, the additional edge creates a single cycle in the graph. Our task is to identify and remove this redundant edge, restoring the graph to a tree. The graph is represented as an array edges of n edges, where each edge connects two different nodes from 1 to n, and n is the number of nodes in the tree. The goal is to find the redundant edge that can be removed to make the graph a tree again. If there are multiple redundant edges, we need to return the one that appears last in the edges array. This problem checks the understanding of graph properties, specifically tree structures, and graph algorithms.

Flowchart Walkthrough

In analyzing the problem specified as LeetCode 684. Redundant Connection with the help of the Flowchart, here's a detailed step-by-step walk-through to determine the appropriate algorithm:

Is it a graph?

  • Yes: The problem explicitly deals with a graph that is represented by edges attempting to form a tree but includes a redundant connection.

Is it a tree?

  • No: Even though the aim is to have a tree, the existance of a redundant edge means that it is not a true tree as it forms a cycle.

Is the problem related to directed acyclic graphs (DAGs)?

  • No: The problem concerns finding a redundant connection in an undirected graph, not related to directed graphs.

Is the problem related to shortest paths?

  • No: The issue is about finding a redundancy in the structure that prevents it from being a tree, not about measuring distances or paths.

Does the problem involve connectivity?

  • Yes: The main task is to determine a way to handle the connectivity of the graph with an extra edge, effectively needing an algorithm to determine connectivity and find the surplus connection.

Is the graph weighted?

  • No: The graph discussed is unweighted; it is only concerned with connectivity without any cost associated with the edges.

Conclusion: Based on the responses navigated through the flowchart, we come to understand that although Depth-First Search (DFS) isn't directly mentioned, it is an appropriate choice for exploring all nodes connected directly or indirectly to determine if adding a new edge would form a cycle or not (a vital detail for identifying redundancy in connections when forming a tree). The use of a Disjoint Set Union could also be considered as it effectively manages connectivity queries and is efficient for cycle detection in this scenario. However, as your interest points towards DFS, this would primarily involve using DFS to identify cycles in the graph, which indicates the presence of redundant connections.

Intuition

The intuition behind this solution is based on the Union-Find algorithm, which is a classic data structure for keeping track of disjoint sets. The idea is to iterate through the list of edges and connect the nodes using the Union operation. We start by initializing a parent array p, representing each node's parent in the disjoint set. Initially, each node is its own parent, indicating that they are each in separate sets.

As we process the edges, we use a Find operation, implemented as the find function, to determine the set representative (parent) for each node. If the nodes connected by the current edge already have the same parent, it means that adding this edge would form a cycle, which is contrary to the tree definition. When we identify such an edge, we know it’s redundant and must be removed.

The clever part of the algorithm is the use of path compression in the Find operation. This optimization steps speeds up subsequent queries for the set representative by making each node along the path point to the ultimate parent directly.

Therefore, when we come across an edge connecting two nodes that are already in the same set (have the same parent), this edge is the redundant one, and we should return it as the answer. In the case that we process all edges without returning any, though highly unlikely for this problem's constraints, we return an empty list. However, since the problem states there's always one additional edge, we're guaranteed to find a redundant connection during our iteration through the edge list.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The solution approach involves the following steps, which are implemented with the Union-Find algorithm:

  1. Initialization: We initialize an array p with 1010 elements, which is assumed to be more than enough to cover the node labels up to n. Here, each element is initialized to its index value, i.e., p[i] = i. This means each node starts as the parent of itself, representing a unique set for each node.

  2. Union-Find Algorithm:

    • The key operations in the Union-Find algorithm are find and union.

    • Find Operation: This operation is implemented as a recursive function:

      def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

      The find function aims to locate the representative or the "parent" of the set that a node belongs to. If the node's parent is not itself, it proceeds to find the ultimate parent recursively and applies path compression by setting p[x] to the ultimate parent. This optimizes the data structure so that subsequent find operations are faster.

    • Union Operation: This operation is implicitly handled within the for loop:

      for a, b in edges:
    if find(a) == find(b):
        return [a, b]
    p[find(a)] = find(b)

      For each edge (a, b) in edges, we first find the parent of both a and b. If they have the same parent, we found our redundant edge which is returned immediately because adding it to the tree would create a cycle. Otherwise, we perform the union by setting the parent of node a's set to be the parent of node b's set, effectively merging the two sets.

  3. Returning the Result:

    • The loop iterates over each edge only once and the redundant edge will be found during this iteration because we're guaranteed there is exactly one extra edge that creates a cycle.

    • The function return [a, b] statement is triggered when a redundant connection is found, which is the edge that causes the cycle.

    • If the loop finishes without finding a redundant edge (which should not happen given the problem constraints), the function defaults to returning an empty list by return [].

In summary, the solution leverages the efficient Union-Find data structure with path compression to identify a cycle in the graph, which is the signature of the redundant connection in an otherwise acyclic tree structure.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example graph to illustrate the solution approach as described. Suppose our graph, which was originally a tree, has 4 nodes, and the edges array is as follows: [[1, 2], [2, 3], [3, 1], [4, 3]]. We can already see that there is a cycle formed by the edges [1, 2], [2, 3], and [3, 1]. According to the problem statement, we need to find the redundant edge that appears last in the edges list, which upon a preliminary look seems to be [3, 1].

  1. Initialization:

    We initialize our parent array p with enough space for our 4 nodes (in reality, our solution sets this up for more nodes, but for simplicity, here we'll limit it to the nodes we have). Thus, p = [0, 1, 2, 3, 4] (we include 0 just to match the node indices with their parent indices for convenience).

  2. Union-Find Algorithm:

    We iterate through the edges array using the find and union operations as described:

    • For the first edge [1, 2], we find the parents of 1 and 2, which are themselves, so we unite them by setting p[find(1)] = find(2). Now p becomes [0, 2, 2, 3, 4].

    • For the second edge [2, 3], we find the parents of 2 and 3, which are 2 and 3 respectively. Since they are different, we unite them by setting p[find(2)] = find(3). Now p becomes [0, 3, 2, 3, 4] and after path compression [0, 3, 3, 3, 4].

    • For the third edge [3, 1], we find the parents of 3 and 1. Both are 3 due to the path compression that has already occurred, indicating we've encountered a cycle. As this is the redundant edge we're looking for, we immediately return [3, 1].

    • The fourth edge [4, 3] does not get processed as we've already found and returned the redundant edge in the step above.

  3. Returning the Result:

    • We successfully find that [3, 1] is the redundant edge that creates a cycle in the graph.

    • The function returns [3, 1] as the answer, which is the edge that must be removed to eliminate the cycle and restore the graph to a proper tree.

In this example, we can see that the Union-Find algorithm effectively identifies the edge causing a cycle due to the immediate parent check in the find operation, assisted by the path compression that optimizes this check as we progress through the array of edges.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
5        # Function to find the set leader using path compression.
6        def find_set_leader(vertex):
7            # If the parent of the current vertex is not itself,
8            # recursively find the set leader and apply path compression.
9            if parent[vertex] != vertex:
10                parent[vertex] = find_set_leader(parent[vertex])
11            return parent[vertex]
12
13        # Initialize the parent array, with each vertex as its own set leader at the start.
14        parent = list(range(len(edges) + 1))
15      
16        # Iterate through all the edges and apply union-find.
17        for a, b in edges:
18            # Find the set leaders for both vertices of the edge.
19            leader_a = find_set_leader(a)
20            leader_b = find_set_leader(b)
21          
22            # If both vertices have the same set leader, a cycle is found, return the edge.
23            if leader_a == leader_b:
24                return [a, b]
25          
26            # Union step: assign vertex b's leader to be the leader of vertex a's set.
27            parent[leader_a] = leader_b
28      
29        # If no redundant connection found (no cycle), return an empty list.
30        return []
31
32# Example usage:
33# sol = Solution()
34# print(sol.findRedundantConnection([[1,2], [1,3], [2,3]]))  # Output: [2, 3]
35
1class Solution {
2
3    // Array representing the parents of each node in the disjoint-set (union-find).
4    private int[] parent;
5
6    // Function to find the redundant connection, taking edges of a graph.
7    public int[] findRedundantConnection(int[][] edges) {
8
9        // Initialize the parent array for a maximum of 1010 nodes.
10        parent = new int[1010];
11        for (int i = 0; i < parent.length; i++) {
12            // Initially, each node is its own parent (self loop).
13            parent[i] = i;
14        }
15
16        // Iterate through all edges.
17        for (int[] edge : edges) {
18            int node1 = edge[0];
19            int node2 = edge[1];
20
21            // If both nodes have the same parent, the edge is redundant.
22            if (find(node1) == find(node2)) {
23                return edge;
24            }
25
26            // Union the sets of two nodes by setting the parent of one as the other.
27            parent[find(node1)] = find(node2);
28        }
29      
30        // If no redundant connection is found, return null (should not happen according to the problem statement).
31        return null;
32    }
33
34    // Recursive function to find the parent of a given node.
35    private int find(int node) {
36
37        // Path compression: if the node is not its own parent, recursively find its parent and update the reference.
38        if (parent[node] != node) {
39            parent[node] = find(parent[node]);
40        }
41        // Return the parent of the node.
42        return parent[node];
43    }
44}
45
1#include <vector>
2using std::vector;
3
4class Solution {
5public:
6    // Parent array for Union-Find structure.
7    vector<int> parent;
8
9    // Function to find redundant connection in a graph represented as an edge list.
10    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
11        // Initialize the parent array for Union-Find, with self-pointing indices.
12        parent.resize(1010);
13        for (int i = 0; i < parent.size(); ++i) parent[i] = i;
14
15        // Iterate over the edges.
16        for (auto& edge : edges) {
17            int nodeA = edge[0], nodeB = edge[1];
18            // Check if merging two sets creates a cycle (i.e., they have the same parent).
19            if (find(nodeA) == find(nodeB)) return edge; // If yes, then current edge is redundant.
20            // Union the two sets.
21            parent[find(nodeA)] = find(nodeB);
22        }
23        // If no redundant edge is found (which shouldn't happen), return an empty array.
24        return {};
25    }
26
27    // Helper function to find the root parent of a node, with path compression.
28    int find(int node) {
29        if (parent[node] != node) { // Check if node is not its own parent (not root node).
30            parent[node] = find(parent[node]); // Recursively find and set the root node.
31        }
32        return parent[node]; // Return the root node.
33    }
34};
35
1/**
2 * Function to find the redundant connection in a graph.
3 * Returns the edge that, when removed, would convert a graph into a tree (a graph with no cycles).
4 * The graph is represented as a list of edges.
5 *
6 * @param {number[][]} edges - A list of pairs representing the undirected edges of the graph.
7 * @return {number[]} - The redundant edge that forms a cycle in the graph.
8 */
9const findRedundantConnection = (edges: number[][]): number[] => {
10    // parent array to keep track of the root parent of each node in the graph.
11    const parent: number[] = Array.from({ length: 1010 }, (_, index) => index);
12
13    /**
14     * Helper function to find the root parent of a node.
15     * Implements path compression to optimize the union-find structure.
16     *
17     * @param {number} node - The node to find the root parent for.
18     * @return {number} - The root parent of the node.
19     */
20    function find(node: number): number {
21        if (parent[node] !== node) {
22            parent[node] = find(parent[node]);
23        }
24        return parent[node];
25    }
26
27    // Iterate through each edge to find the redundant connection.
28    for (let [nodeA, nodeB] of edges) {
29        // If the two nodes have the same root parent, a cycle is detected.
30        if (find(nodeA) === find(nodeB)) {
31            return [nodeA, nodeB];
32        }
33        // Union the sets.
34        parent[find(nodeA)] = find(nodeB);
35    }
36
37    // If no redundant connection is found, return an empty array.
38    return [];
39};
40
41export { findRedundantConnection }; // Optional: Use this if you want to import the function elsewhere.
42

Time and Space Complexity

The given code implements a Union-Find algorithm to detect a redundant connection in a graph. Let's analyze the time and space complexity:

Time Complexity

The time complexity of the Union-Find algorithm primarily depends on the two operations: find and union. Each edge triggers both operations once.

  • The find operation uses path compression, which gives us an amortized time complexity of almost constant time, "O(α(n))", where α is the Inverse Ackermann function and is very slowly growing, therefore it's nearly constant for all practical purposes.

  • The union takes "O(1)" time since it's just assigning the root of one element to another.

Since the operations are performed for each edge and there are "E" edges, the amortized time complexity of the algorithm is "O(Eα(n))", which simplifies to "O(E)" considering the very slow growth of α(n).

Space Complexity

For space complexity, we have:

  • An array p, which stores the parents of each node in the graph. The size of the array is fixed at 1010, therefore, it requires "O(1)" space since it's a constant space and doesn't depend on the size of the input.

Thus, the overall space complexity of the given code is "O(1)".

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Want a Structured Path to Master System Design Too? Don’t Miss This!