Dynamic connectivity
When cables are added over time, repeated graph searches can redo the same work. A disjoint set keeps one representative for each connected group. Finding two equal representatives proves that a proposed cable stays inside an existing group. Joining different representatives merges groups and reduces the component count once. A repeated cable must not merge a group with itself.
Sizes belong to representatives, so always find the current representative before reading a size. For weighted cabling, sort candidate edges and accept only those joining different groups. For threshold queries, sort the queries too and add every edge that has become eligible. The input order can still matter to the requested output; preserve original query indices. These exercises move from single unions to offline processing with a strict weight boundary.
cables = [[0,1], [2,3], [1,2], [0,3]]
component counts = [3,2,1,1]
largest sizes = [2,2,4,4]
first redundant cable index = 3
The last cable joins vertices already represented by the same component.