Day: June 30, 2025

Set Partitions The incremental connectivity problem is equivalent to maintaining a partition of a set. Initially, each node belongs to its own set. As edges are added, the sets at the endpoints become connected and are merged together. Querying for connectivity is equivalent to querying for whether two elements belong to the same set.