complexitydsagraphs
Union-find fits repeated connectivity queries
Anonymous
Union-find works well for repeated connectivity queries when edges only get added. Path compression shortens find paths, while union by size attaches the smaller tree under the larger one. Together, operations are amortized O(alpha(n)) per operation. Arbitrary edge deletions need extra machinery.
0