Problem: Redundant Connection Task: You have a tree plus one extra edge (making exactly one cycle). Find the extra edge. This is cycle detection in action. Process edges in order. The first edge where both endpoints are already connected is the answer. DSU makes this clean and efficient.
The problem guarantees edges are given in order, and you must return the last one that creates a cycle. Initialize DSU with nodes, then iterate through the edge list. Time: , which is almost .