Solve a graph problem using Disjoint Set Union (DSU)

This problem involves a graph scenario best solved using the Disjoint Set Union (DSU) (also known as Union-Find) data structure. DSU efficiently tracks connected components and supports two core operations in near O(1) amortized time (with path compression + union by rank):

• find(x): Returns the root/representative of x's component
• union(x, y): Merges the components containing x and y

Common problem patterns that map to DSU:

• Detecting cycles in an undirected graph
• Finding the number of connected components
• Minimum spanning tree (Kruskal's algorithm)
• Dynamic connectivity queries
• Redundant connection / critical edges
• Accounts merge, friend circles, network connectivity

Key implementation details to know:

1. Path compression in find() — flatten the tree for future lookups
2. Union by rank/size — always attach the smaller tree under the larger to keep the tree shallow
3. Track component count by decrementing on successful unions

Complexity: O(α(N)) per operation where α is the inverse Ackermann function — effectively O(1) for all practical inputs.

Approach tips: First, model the problem as a graph — identify nodes and edges. Then decide if the query is about reachability/connectivity between nodes, which is the sweet spot for DSU. If the problem involves edge weights or ordering (e.g., process edges in sorted order), consider combining DSU with a greedy strategy like in Kruskal's MST.