According to Wikipedia:
A dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph.
And:
A union–find data structure is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
At first glance, there is little relationship between these data structures. But almost every article, that mentions dynamic connectivity, glimpses at union-find too. So, I wonder how are these two related?
From the Wikipedia article about dynamic connectivity:
The set V of vertices of the graph is fixed, but the set E of edges can change. The three cases, in order of difficulty, are:
- Edges are only added to the graph (this can be called incremental connectivity);
- Edges are only deleted from the graph (this can be called decremental connectivity);
- Edges can be either added or deleted (this can be called fully dynamic connectivity).
A union-find data structure (also known as a disjoint set data structure) can be used in the first case. You can use the union operation to join two components when adding an edge, and the find operation to test whether two vertices are in the same component. However, a union-find data structure has no operation to support deleting an edge, splitting a component into two newly-disconnected components; so it cannot be used to solve the other two cases of the dynamic connectivity problem.