684. Redundant Connection

How to solve Redundant Connection (LeetCode 684): the approach in brief

The problem

In this problem, a tree is an undirected graph that is connected and has no cycles.

Pattern

Redundant Connection is a Graph Traversal Patterns (DFS & BFS) problem, in the Union-Find (Disjoint Set Union - DSU) subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Master Union-Find data structure with path compression and union by rank for connectivity problems.

Approach outline

1. Recall that the problem involves detecting cycles in an undirected graph, which can be efficiently managed using specific data structures.
2. Consider using the Union-Find (Disjoint Set Union) data structure to keep track of connected components as you process each edge.
3. As you iterate through the edges, try to union the sets of the two vertices; if they are already in the same set, adding this edge creates a cycle.

Complexity

The reference solution runs in O(n * α(n)) time and O(n) space.

Asked at

Redundant Connection has been reported in interviews at Amazon.