Introduction

Redundant Connection is one of the most important Union Find (Disjoint Set Union - DSU) problems.

You are given:

  • An undirected graph
  • The graph was originally a tree
  • One additional edge was added

Goal

Find the edge that creates a cycle in the graph.

Example

Input

[[1,2],[1,3],[2,3]]

Output

[2,3]

Explanation

1|\
| \
2--3

The edge (2,3) creates a cycle.

Key Observation

A tree always contains:

 n nodesn - 1 edges
No cycles

If two nodes already belong to the same connected component and we try to connect them again:

Cycle Found

Therefore:

Union Find (DSU)

is the ideal solution.

Algorithm

  1. Initialize parent array.
  2. Process each edge one by one.
  3. Find parent of both nodes.
  4. If both parents are same:
    • Cycle detected.
    • Return current edge.
  5. Otherwise union both sets.
  6. Continue until answer is found.

Dry Run

Input

[[1,2],[1,3],[2,3]]

Initially

Parent
1 → 1
2 → 2
3 → 3

Process Edge (1,2)

Union(1,2)
Parent
1 → 2
2 → 2
3 → 3

Process Edge (1,3)

Union(1,3)
Parent
1 → 2
2 → 3
3 → 3

Process Edge (2,3)

Find(2) = 3Find(3) = 3

Both nodes already belong to the same component.

Cycle Detected

Answer

[2,3]

Approach : Union Find (DSU)

Explanation

Initially every node belongs to its own component.

For every edge:

  • Find ultimate parent of both nodes.
  • If parents are same:
    • Edge creates a cycle.
    • Return the edge.
  • Otherwise merge the two components.

Union Find efficiently tracks connectivity while detecting cycles.

Practice

Complexity Analysis

Time Complexity: O(n × α(n))
Explanation: Each Union and Find operation takes nearly constant time due to path compression. We process every edge once.

Space Complexity: O(n)Explanation: An extra parent array of size n is used to store the representative of each node.

Why This Problem is Important

This problem helps you learn:

  • Union Find (DSU)
  • Cycle Detection
  • Graph Connectivity
  • Connected Components
  • Efficient Graph Processing

Common Beginner Mistakes

  • Forgetting path compression.
  • Using DFS for every edge.
  • Performing union before cycle check.
  • Incorrect parent initialization.
  • Using wrong array size.

Interview Tip

Always mention:

If two nodes already belong to the same connected component, adding another edge between them creates a cycle.

This observation directly leads to the Union Find solution.

Related Questions

  • Number of Connected Components in an Undirected Graph
  • Accounts Merge
  • Graph Valid Tree
  • Number of Provinces
  • Kruskal's Algorithm
  • Making A Large Island

Final Takeaway

Redundant Connection is a classic Union Find (DSU) problem.

It teaches:

  • Cycle Detection
  • Connected Components
  • Path Compression
  • Graph Connectivity
  • Efficient DSU Operations

Mastering this problem makes advanced Union Find and graph interview questions significantly easier