The dynamic connectivity problem is the following:
Maintain an undirected graph G so that edges may be inserted an deleted and connectivity queries may be answered efficiently.
Goal: Support these three operations:
● link(u, v): Add in edge {u, v}. The assumption is that u and v are in separate trees.
● cut(u, v): Cut the edge {u, v}. The assumption is that the edge exists in the tree.
● are-connected(u, v): Return whether u and v are connected.
The data structure developed can perform these operations time O(log n) each.