Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Redundant Connection

Explore how to use the Union Find algorithm to detect and remove redundant connections in an undirected graph. This lesson helps you understand how to transform a graph with cycles into a tree by efficiently finding edges that can be removed, reinforcing connectivity and cycle detection concepts.

We'll cover the following...

Statement

We’re given an undirected graph consisting of nn nodes. The graph is represented as list 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.

Example

canvasAnimation-image
1 / 5

Understand the problem

Let’s take a moment to make sure we have correctly understood the problem. The quiz below helps us to check that we are solving precisely the right problem:

Redundant Connection

1.

What is the output if the following list of edges is provided as input?

edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

A.

[2, 3]

B.

[3, 4]

C.

[1, 4]

D.

[1, 5]

1 / 2

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3

Try it yourself

Implement your solution in main.py in the following coding playground. You will need the provided supporting code to implement your solution.

Note: To solve this problem, you may need to change the implementation of the functions in the given Union Find class.

Python
usercode > main.py
"""

⬅️ We have provided a union_find.py file under the "Files" tab 

of this widget. You can use this file to build your solution.

"""

from union_find import UnionFind





def redundant_connection(edges):

    

    # Replace this placeholder return statement with your code

    return []
Redundant Connection