Solution: Redundant Connection

Statement

We’re given an undirected graph consisting of $n$ nodes. The graph is represented as list called edges, of length $n$, 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 $n$ nodes. If there are multiple candidates for removal, return the edge that occurs last in edges.

Constraints:

• $3 \leq$ $n$ $\leq 100$
• edges.length$=$ $n$
• edges[i].length $=$ 2
• $1 \leq$ a $<$ b $\leq n$
• $a \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(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